Please explain, why the idea of state like “computing the minimum cost to ith matrix” doesn’t work in this case, or in the more general case . I am a bit confused about when to go for i to j state .
Defining states in Matrix Multiplication
@Vishal_234 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].