Matrix chain multiplication

Question

Which of the following is the recurrence relation for the matrix chain multiplication problem where p[i-1]*p[i] gives the dimension of the i^th matrix?

1.   dp[i,j]=1 if i=j
   dp[i,j]=min{dp[i,k]+dp[k+1,j]}
2.   dp[i,j]=1 if i=j
   dp[i,j]=min{dp[i,k]+dp[k+1,j]}+p[i-1]*p[k]*p[j]
3.   dp[i,j]=0 if i=j
   dp[i,j]=min{dp[i,k]+dp[k+1,j]}
4.   dp[i,j]=0 if i=j
   dp[i,j]=min{dp[i,k]+dp[k+1,j]}+p[i-1]*p[k]*p[j]

Comments

4th option is the correct one.

Answer 1

....

Answer 2

Option 4 is the correct one. For detail explanation http://pegasus.uprm.edu/xryong/COMP6785/L12/L12.pdf

Answer 3

Check below image................................