DP-Matrix Chain Order

Analyze Question

This is a simple example to understand matrix chain order in DP.
As we know, all the DP problem can be solve by three basic criteria

1. find the optimized sub problem

   In matrix multiplication , the cost of multiplication of matrix is different between the different multi sequence.for e.g. we have 3 matrix

   A: 10X100

   B: 100x5

   C: 5x50

   then if we follow diff multiplication sequence

   for ((A1A2)A3) : A1A2=$10\times 100 \times 5 = 5000 $ A3=$10\times5\times50 = 2500$ tot: 7500

   for(A1(A2A3)): A2A3=$100 \times 5 \times 50 = 25000$ A1 = $10\times100\times50=50000$ tot:75000

   and thus its 10 times bigger for the last approach than the first approach

   and in DP we suppose if we already know the best solution for the matrix multiplication, for e.g. (A1A2A3A4)(A5A6A7) , if we separate them into subarrays ((A1A2A3)A4) (A5(A6A7)) the subarray it self should also be the optimized multiplication.

2. solving the sub problems

   according to the book(Introduction to algorithm), if we define $m[i,j]$ as recurrence,

   1. if $i=j$ then we reach the base case as $A_{i=j}$ do not need any multiplications. and we can safely conclude that $m[i,i]=0 \space \forall i\in1,2,…,n$ and we call this step 1

   2. suppose we separate the Arrays from $k$ , that said, we separate into two groups, $A_i,A_{i+1},A_{i+2}…A_k$ and $A_{k+1},A_{k+2}..A_{j}$ where $i\leq k < j$

   3. Then in this phase we can say the to calculate $m[i,j]$ equal to calculate the sub arrays from $A_{i..k}$ and $A_{k+1..j}$ , and also should add the minimal $k$ where cause the minimal multiplication value in this phase and we will called it $p_{i-1}p_kp_j$

   4. So the recurrence relations should like
      $$
      m[i,j]=
      \begin{cases}
      0& \text{i=j}\
      min_{i\leq k <j}(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j)& \text{n = 1}\
      \end{cases}
      $$

3. Down top solution

   we should doing our procedure from the base case to the beginning to get our answer.

Example

Step 1

Separate into two arrays

No need to find min because there is only one possibilities for each part

A1A2 $30 \times 35 \times 15 = 15750$

A2A3 $35\times14\times5=2625$

A3A4 $15\times5\times 10=750$

A5A6 $10\times20\times25=5000$

Step 2

Separate into three arrays

A1A2A3 has two variations (A1A2)A3 or A1(A2A3) we will compare this two steps

(A1A2)A3 = $15750+30\times15\times5=18000$ A1(A2A3)=$2625+30\times35\times5=7875$ for smaller part we choose later one

same to other part

A2(A3A4) = $750+15\times10\times20=6000$ (A2A3)A4=$2625+35\times5\times10=4375$ choose 4375

A3(A4A5)=$1000+15\times5\times20=2500$ (A3A4)A5=$750+25\times10\times20=3750$ choose 2500

A4(A5A6)=$5000+5\times10\times25=6250$ (A4A5)A6 = $1000+5\times20\times25=3500$ choose 3500

Step3

we proceed these steps from separate into 1 to 6 until reach the final one: A1..A6 separation

A1(A2A3A4A5A6) : 44750

(A1A2)(A3A4A5A6): 32375

(A1A2A3)(A4A5A6): 15125

(A1A2A3A4)(A5A6):21875

(A1A2A3A4A5)A6: 30375

we choose 15125 (A1A2A3)(A4A5A6)

and its sub arrays should be

(A1(A2A3))((A4A5)A6)