# Matrix Chain Multiplication – Dynamic Programming

### Matrix Chain Multiplication Problem Statement:

Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension

p[i-1] x p[i].

We need to write a function MatrixChainOrder() that should return the minimum number of multiplications needed to multiply the chain.

The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

Givne 4 matrices A_{1} A_{2} A_{3 }A_{4 }, we need they can be parenthesised as

(A_{1} (A_{2} (A_{3 }A_{4})))

(A_{1} ((A_{2} A_{3 })A_{4}))

((A_{1} A_{2} )(A_{3 }A_{4}))

(((A_{1} A_{2 })A_{3 })A_{4})

The order in which we parenthesize the product of matrices affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A_{1} is a 10 × 100 matrix, A_{2} is a 100 × 5 matrix, and A_{3 }is a 5 × 50 matrix. (To mulitply A_{p*q} *A_{q*r} we need p*q*r number of operations). Then,

(A_{1}A_{2})A_{3}= (10×100×5) + (10×5×50) = 5,000 + 2,500 = 7,500 operations A_{1}(A_{2}A_{3}) = (100×5×50) + (10×100×50) = 25,000 + 50,000 = 75,000 operations.

Thus how we parenthesize plays a very important role.

### Matrix Chain Multiplication Examples:

Input: p[] = {30, 35, 15, 5, 10, 20, 25}Output: 15125There are 6 matrices of dimensions 30x35, 35x15, 15x5, 5x10, 10x20, 20x25. Let the input 6 matrices be A_{1}, A_{2}, A_{3},A_{4},A_{5},and A_{6}. The minimum number of multiplications are obtained by putting parenthesis in following way ((A_{1}(A_{2}A_{3}))((A_{4}A_{5}) A_{6}) --> 15,125Input: p[] = {10, 20, 30, 40, 30}Output: 30000There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30. Let the input 4 matrices be A, B, C and D. The minimum number of multiplications are obtained by putting parenthesis in following way (((AB)C)D) --> 30,000

### Matrix Chain Multiplication Solution:

#### Matrix Chain Multiplication Video Explanation:

To help us keep track of solutions to subproblems, we will use a table, and build the table in a bottomup manner. For 1 ≤ *i* ≤ *j *≤ *n*, let *m*[*i*, *j*] be the minimum number of scalar multiplications needed to compute the *A*_{i..j}. The optimum cost can be described by the following recursive formulation.

**State of DP:**

let *m*[*i*, *j*] be the minimum number of scalar multiplications needed to compute the *A*_{i..j}.

let

*m*[

*i*,

*j*] be the minimum number of scalar multiplications needed to compute the

*A*

_{i..j}.

Basis: Observe that if *i* = *j* then the problem is trivial; the sequence contains only one matrix, and so the cost is 0. (In other words, there is nothing to multiply.) Thus,

*m[i, i] = 0 for i = 1, 2, …, n. *

Step: If *i* ≠ *j*, then we are asking about the product of the subchain *A*_{i..j }and we take advantage of the structure of an optimal solution. We assume that the optimal parenthesization splits the product, *A*_{i..j} into for each value of *k*, 1 ≤ *k* ≤ *n* − 1 as *A*_{i..k} *. A*_{k+1..j}.

The optimum time to compute is *m*[*i*, *k*], and the optimum time to compute is *m*[*k* + 1, *j*]. We may assume that these values have been computed previously and stored in our array. Since *A*_{i..k }is a matrix, and *A*_{k+1..j }is a matrix, the time to multiply them is *p*_{i − 1 }.* p*_{k} . *p** _{j}. *This suggests the following recursive rule for computing

*m*[

*i*,

*j*].

**Recursion for DP:**

To keep track of optimal subsolutions, we store the value of *k* in a table *s*[*i*, *j*]. Recall, *k* is the place at which we split the product *A*_{i..j} to get an optimal parenthesization. That is,

*s*[*i*, *j*] = *k* such that *m*[*i*, *j*] = *m*[*i*, *k*] + *m*[*k* + 1, *j*] + *p*_{i − 1 }.* p*_{k} . *p _{j}.*

**Implementing the Rule**

In Dynamic Programming we reuse stored values, in our problem the only tricky part is arranging the order in which to compute the values (so that it is readily available when we need it).

In the process of computing *m*[*i*,*j*] we will need to access values *m*[*i*,* k*] and *m*[*k* + 1, *j*] for each value of *k* lying between *i* and *j*. This suggests that we should organize our computation according to the number of matrices in the subchain. So, lets work on the subchain:

Let **L = j − i + 1 denote the length of the subchain being multiplied**.

The subchains of length 1 (

*m*[

*i*,

*i*]) are trivial. Then we build up by computing the subchains of length 2, 3, …,

*n*. The final answer is

*m*[1,

*n*].

Now set up the loop: Observe that if a subchain of length L starts at position *i*, then *j* = *i* + L − 1. Since, we would like to keep *j* in bounds, this means we want *j* ≤ *n*, this, in turn, means that we want *i* + L − 1 ≤ *n*, actually what we are saying here is that we want *i* ≤ *n* − L +1. This gives us the closed interval for *i*. So our loop for *i* runs from 1 to *n* − L + 1.

**Algorithm:
(It is stated as given in the CLRS book)**

Matrix-Chain(arrayp[1 ..n], intn) { Arrays[1 ..n− 1, 2 ..n];FORi= 1TOnDOm[i,i] = 0; // initializeFORL = 2TOnDO{ // L=length of subchainFORi= 1TOn− L + 1 do {j=i+ L − 1;m[i,j] = infinity;FORk=iTOj− 1DO{ // check all splitsq=m[i,k] +m[k+ 1,j] +p[i− 1]p[k]p[j];IF(q< m[i,j]) {m[i,j] =q;s[i,j] =k; } } } } returnm[1,n](final cost) ands(splitting markers); }

**Example **[on page 337 in CLRS]: The *m*-table computed by MatrixChain procedure for *n* = 6 matrices *A*_{1}, *A*_{2},* A*_{3},* A*_{4},* A*_{5},* A*_{6} and their dimensions 30, 35, 15, 5, 10, 20, 25.

Note that the m-table is rotated so that the main diagonal runs horizontally. Only the main diagonal and upper triangle is used.

**Our required parenthesized matrices are (( A_{1}(A_{2} A_{3}))((A_{4} A_{5}) A_{6})**

### Matrix Chain Multiplication Solution code:

Here is the working code:

#include<bits/stdc++.h> using namespace std; /*Matrix Ai has dimension p[i-1] x p[i] for i = 1..n*/ int MatrixChainOrder(int p[], int n) { int m[n][n]; int i, j, k, L, q; /* m[i,j] = Minimum number of scalar multiplications needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is p[i-1] x p[i] */ /*cost is zero when multiplying one matrix.*/ for (i = 1; i < n; i++) m[i][i] = 0; /*L is chain length. */ for (L=2; L<n; L++) { for (i=1; i<=n-L+1; i++) { j = i+L-1; m[i][j] = INT_MAX; for (k=i; k<=j-1; k++) { // q = cost/scalar multiplications q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if (q < m[i][j]) m[i][j] = q; } } } return m[1][n-1]; } int main() { int arr[] = {30, 35, 15, 5, 10, 20, 25}; int size = sizeof(arr)/sizeof(arr[0]); cout<<"Minimum number of multiplications is:\n"; cout<<MatrixChainOrder(arr, size); return 0; }

**Output:**

Minimum number of multiplications is: 15125

**Time Complexity: O(N ^{3})
Auxiliary Space: O(N^{2})**