# Matrix chain multiplication using dynamic programming

Problem here is, we are given N matrices. Dimensions of each matrix given in an array P where P[i-1] and P[i] denote rows and column respectively of ith matrix. We need to find an order in which these matrices are multiplied, so that total number of scalar multiplications are least. Matrix chain multiplication is a typical problem which is used to explain dynamic programming. Approach learnt here can be easily applied to many other problems.

Before going further, lets understand some points about matrix multiplication
1. Matrix multiplication is associative i.e.  A* (B*C) = (A*B) *C
2. It is not commutative i.e  A * (B*C) not equal to A * (C * B)
3. To multiply two matrices, they should be compatible i.e. no of columns in first matrix should be equal to number of rows of second matrix.
Let’s get back to problem.  Easy way to understand the problem is to say we need to figure out a way to put parenthesis around matrices so that total number of multiplication are least.

Brute force way of doing this to find out every possible combination of parenthesis and check which one is minimum.
This algorithm is exponential in time and hence of no use for every large input.

Let’s see if dynamic programming fit in.

We can see that cost of multiplying matrices Ai to Aj  is cost of (Ai to Ak) + (Ak+1 to Aj )+
(P[i] * P[k-1] * P[j]).
Idea is to find out K such that later expression becomes minimum. M[i,j] represents the cost to multiply matrix i to matrix j

M[i,j]  = M[i,k] + M[K+1,j] + ((P[i] * P[k-1] * P[j]) )

So when we are calculating M[i,j] we should already have M[i,k] and M[k+1,j].
We also know that M[i,i] = 0 as multiplying a single matrix will be 0.

Looking at the requirement to calculate M[i,j], we can say that it depends on the length of the chain.
Length of chain from matrix i to matrix j would be i+j-1.

We start with length 2 and go on to solve the table entry for length N. M[1, N] will give us the final cost. Since we need to start at every position for every length,
then i + L -1 = j. Also, j<=N; hence i <= N-L+1.

## Code for multiplication of matrix problem

### Complexity analysis

Time complexity of matrix chain multiplication using dynamic programming is O(N*N). Also space complexity is O(N*N).