Dynamic programming matrix chain multiplication

Question

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-matrix-chain-multiplication/

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;
    }
}

Thanks!

Dude, geeksforgeeks is a very high quality blog. You can trust in every line of code that is placed there! — xenteros
– xenteros, Commented Jul 22, 2016 at 12:00

Jakube · Accepted Answer · 2016-07-22 11:57:25Z

1

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.

Although I have a few optimizations:

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;
}

edited Jul 22, 2016 at 11:57

answered Jul 22, 2016 at 11:07

Jakube

3,6124 gold badges26 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Dynamic programming matrix chain multiplication

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related