I am solving this problem (https://leetcode.com/problems/minimum-cost-to-merge-stones/ ).
The solution uses 3-D dp with following transitions:-
1) dp[i][j][m] means the cost needed to merge stone[i] ~ stones[j] into m piles.
Initial status dp[i][i][1] = 0 and dp[i][i][m] = infinity.
2) dp[i][j][m] = min(dp[i][mid][1] + dp[mid + 1][j][m — 1])
I am not able to understand the 2nd transition properly. Why are we trying to merge stones i~mid into only 1 stone and not considering other possibilities ? Shouldn't the transition be dp[i][j][m]=min(dp[i][j][m],dp[i][mid][x]+dp[mid+1][j][m-x]) for x in range(1,m-1) ?
Thanks.
Why downvotes ?
When you merge $$$m$$$ piles into one, each of those $$$m$$$ piles comes from some initial interval. In this transition,
midis the end of the first of those $$$m$$$ intervals. This means that interval $$$[i, mid]$$$ was merged into one pile already, and this one pile will be first of $$$m$$$ piles that you're combining now.Thanks for replying. I understood the solution now :)