Matrix chain multiplication

#1

can u explain me how we write the recurrence relation in matrix chain

#2

hello @shashankmaheshwari054

let say solve(i,j) tells minimum cost of matrix multiplication of this portion -> [i-1…j].
our base case should be if i==j return 0.
because [i-1…i] is a single matrix.

now we can break the problem at some intermediate point k and solve [i,k] and [k+1,j] part seprately and then add the cost of combining.

solve(i,j)= min ( solve(i,k) + solve(k+1,j) + A[i-1]*A[k]*A[j] <- cost of multiplication of matrix [i-1…k] [k+1…j] )
for k=i…j-1

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.