动态规划矩阵链乘法 [英] Dynamic programming matrix chain multiplication

问题描述

我正在阅读动态编程中的矩阵链乘法，
它有一个幼稚的递归解决方案，它具有指数级的运行时间。

I was reading about the matrix chain multiplication in dynamic programming, It has a naive recursive solution which has a exponential run-time.

http://www.geeksforgeeks.org/dynamic-programming-set- 8-矩阵链乘法/

尽管有动态编排。解决方案（上面的链接中的代码）的运行时复杂度为O（n ^ 3），但是如果我们保留一个2d数组来存储重叠子问题的结果，它的运行时是否与dp解决方案相同？

Although there is dynamic prog. solution(code in the link above) which has a run-time complexity of O(n^3), but if we keep a 2d array to store results for overlapping sub problems, Will it have a same run-time as the dp solution ?

public class MatrixChain {

    public static void main(String... args) throws IOException {
        new MatrixChain().job();
    }

    private void job() {
        int arr[] = new int[]{40, 20, 30, 10, 30};
        int[][] dp = new int[5][5];
        for (int[] x : dp)
            Arrays.fill(x, -1);
        int min = findMin(arr, 1, arr.length - 1, dp);
        System.out.println(min);
    }

    private int findMin(int[] arr, int i, int j, int dp[][]) {
        if (i == j) return 0;
        int min = Integer.MAX_VALUE;
        for (int k = i; k < j; k++) {
            int fp;
            if (dp[i][k] == -1)
                dp[i][k] = fp = findMin(arr, i, k, dp);
            else fp = dp[i][k];
            int lp;
            if (dp[k + 1][j] == -1)
                dp[k + 1][j] = lp = findMin(arr, k + 1, j, dp);
            else
                lp = dp[k + 1][j];

            int sum = fp + lp + arr[i - 1] * arr[k] * arr[j];
            if (sum < min)
                min = sum;
        }
        return min;
    }
}

谢谢！

推荐答案

是的。编写函数是迭代还是递归都没关系。重要的是，您要记住结果。而你做到了。

Yes, it will have. It doesn't matter if you write your function iterative or recursive. The important thing is, that you memorize your results. And that you do.

尽管我做了一些优化：

private int findMin(int[] arr, int i, int j, int dp[][]) {
    if (i == j) 
        return 0;

    /* Immediate look-up in dp */
    if (dp[i][j] != -1)
        return dp[i][j];

    /* Otherwise compute the number, much shorter since you don't
       have to worry about reading from dp and saving it to dp. */
    int min = Integer.MAX_VALUE;
    for (int k = i; k < j; k++) {
        int fp = findMin(arr, i, k, dp);
        int lp = findMin(arr, k + 1, j, dp);
        int sum = fp + lp + arr[i - 1] * arr[k] * arr[j];
        if (sum < min)
            min = sum;
    }

    /* Now save the result */
    dp[i][j] = min;
    return min;
}

这篇关于动态规划矩阵链乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！