Problem Pattern | Matrix Chain Multiplication
If you have seen Balloon Burst and this problem, not able to find the solution .\nJust read the following pattern carefully .\n\nThese both are the child proble
If you have seen Balloon Burst and this problem, not able to find the solution .\nJust read the following pattern carefully .\n\nThese both are the child problem of MCM .\n\nProblem : If a chain of matrices is given, we have to find the minimum number of the correct sequence of matrices to multiply.\n\n\nThe problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.\nNote:no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:\n\n(ABC)D = (AB)(CD) = A(BCD) = ....\nHowever, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A is a 10 \xD7 30 matrix, B is a 30 \xD7 5 matrix, and C is a 5 \xD7 60 matrix. Then,\n\n(AB)C = (10\xD730\xD75) + (10\xD75\xD760) = 1500 + 3000 = 4500 operations\nA(BC) = (30\xD75\xD760) + (10\xD730\xD760) = 9000 + 18000 = 27000 operations.\nClearly the first parenthesization requires less number of operations.\nNote ; We\'ll be given an array arr[ ] which represents the chain of matrices such that the ith matrix arr[i] is of dimension arr[i-1] x arr[i].\nThat\'s why we start out \'k\' i.e partition from \'i\' =1 so that arr[ 1] is of dimentions arr[1-1] * arr[1] else we\'ll get index out of bound error Eg arr[0-1] * arr[0] is not possible\nSo first half of the array is from i to k & other half is from k+1 to j\nAlso we need to find the cost of multiplication of these 2 resultant matrixes (first half & second half) which is nothing but arr[i-1] * arr[k] * arr[j]\n\nRecursion\nHere is the recursive algo :\n\n\nCode\n   ```\n int solve(int i, int j,int arr[])\n    {\n        if(i>=j)return 0;\n\n        int ans=INT_MAX;\n        for(int k=i;k<=j-1;k++)\n        {\n            int tempAns = solve(i,k,arr) + solve(k+1,j,arr)\n                          + arr[i-1]*arr[k]*arr[j];\n            \n            ans=min(ans,tempAns);                        \n        }\n        return ans;\n    }\n    int matrixMultiplication(int N, int arr[])\n    {\n        return solve(1,N-1,arr);\n    }\n```\nThe time complexity of the above naive recursive approach is exponential. Observe that the above function computes the same subproblems again and again.\n\nLet us saywe are given an array of 5 elements that means we are given N-1 i.e 4 matrixes .See the following recursion tree for a matrix chain of size 4.\nimage\n\nThere are so many overlapping subproblems . Let\'s optimize it using DP !!\n\nMemoization\nJust adding a few lines to the above code, we can reduce time complexity from exponential to cubic :\n\n\n```\nint dp[501][501];\n    \n    int solve(int i, int j,int arr[])\n    {\n        if(i>=j)return 0;\n        \n        if(dp[i][j]!=-1)\n        return dp[i][j];\n\n        int ans=INT_MAX;\n        for(int k=i;k<=j-1;k++)\n        {\n            int tempAns = solve(i,k,arr) + solve(k+1,j,arr)\n                          + arr[i-1]*arr[k]*arr[j];\n            \n            ans=min(ans,tempAns);\n                          \n        }\n        return dp[i][j] = ans;\n    }\n    int matrixMultiplication(int N, int arr[])\n    {\n        memset(dp,-1,sizeof(dp));\n        return solve(1,N-1,arr);\n    }\n\t```\n\t\nBottom Up DP\nIt\'s a bit tricky but if you got the above logic then you woudn\'t face any issues. I stil, prefer the Momoization\n\n```\nint MatrixChainOrder(int arr[], int n)\n{\n \n    /* For simplicity of the program, one\n    extra row and one extra column are\n    allocated in arr[][]. 0th row and 0th\n    column of arr[][] are not used */\n    int dp[n][n];\n \n    int i, j, k, L, q;\n \n    /* dp[i, j] = Minimum number of scalar\n    multiplications needed to compute the\n    matrix A[i]A[i+1]...A[j] = A[i..j] where\n    dimension of A[i] is arr[i-1] x arr[i] */\n \n    // cost is zero when multiplying\n    // one matrix.\n    for (i = 1; i < n; i++)\n        dp[i][i] = 0;\n \n    // L is chain length.\n    for (L = 2; L < n; L++)\n    {\n        for (i = 1; i < n - L + 1; i++)\n        {\n            j = i + L - 1;\n            dp[i][j] = INT_MAX;\n            for (k = i; k <= j - 1; k++)\n            {\n                // q = cost/scalar multiplications\n                q = dp[i][k] + dp[k + 1][j]\n                    + arr[i - 1] * arr[k] * arr[j];\n                if (q < dp[i][j])\n                    dp[i][j] = q;\n            }\n        }\n    }\n \n    return dp[1][n - 1];\n}\n```\n
[]