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?
- dp[i,j]=1 if i=j
dp[i,j]=min{dp[i,k]+dp[k+1,j]}
- 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]
- dp[i,j]=0 if i=j
dp[i,j]=min{dp[i,k]+dp[k+1,j]}
- 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]