In matrix chain multiplication,Pls Explain how that state came

#1

He Wrote Like this ; dp[x][y] = min{dp[x][k] + dp[k+1][y] + ar[x]*ar[k+1]*ar[y+1]}
How Did k+1and y+1 came /i didnt understood???

#2

Hello @yashratnani6 have you seen the editorial for this?

#3

@yashratnani6 we are just breaking the matrix into different parts.
read this:
It varies from question to question and realizing what the structure the problem follows and to what extent we can break it down. Now in matrix multiplication we are computing the best way to multiply matrices from any index 1 to i but the thing is how we are doing it and what problems we face while computing it.
Now lets say you have the best way to multiply matrices in some cost matrix up to index i.
So you have cost[1][1] , cost[1][2]…cost[1][i], stored with you. Now we are at an index i+1.
First way is to go like we multiply first i matrices with cost[1][i] and simply add (i+1)th matrix.
Then we say lets multiply first i-1 matrices with cost[1][i-1], and multiply i and (i+1)th matrix separetely, and then add the cost of these 2 resulting matrices.
Now moving on we can say we multiply first i-2 matrices with cost[1][i-2] ,and multiply the remaining three matrices ,i.e., i-1.i and i+1.
But what is the best way to multiply these 3 matrices , we haven’t calculated cost[i-1][i+1] anywhere, have we?
This the reason we have to solve for this as well, because this is a new sub problem and we haven’t solved it yet.
So you can see we are required to solve for every index(2,i) to i+1, to get the result for cost[1][i+1].
if you still have any doubt you can ask here:
Happy Learning!!

#4

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.