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] = 0 and dp[i][i][m] = infinity.
2) dp[i][j][m] = min(dp[i][mid] + 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) ?