In the first approach, the state was dp(I,k) = dp(i-1,k-x) where x ranges from 0to ai , but in the optimization approach state is dp(I,k-1) = dp(I,k) - dp[i-1,k-1 ) + dp(i-1,k-1-ai). How this state relates to the previous state. Please explain.
M-Candies State transition
@Vishal_234
Here the ‘i’ and ‘k’ are just variables for writing this relation.
I also suggest you to rewatch the video, because it is explained well in the video that how these states are related, like in first one we are finding it some things which are already calculated, thats why in second one we have used those things so that the solution can be optimized.
Yes, Sir thanks. I understood it.
1 Like