rr459595's blog

Leetcode problem:- Minimum cost to merge stones.
By rr459595, history, 5 years ago, In English

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.

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why downvotes ?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

When you merge $$$m$$$ piles into one, each of those $$$m$$$ piles comes from some initial interval. In this transition, mid is 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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for replying. I understood the solution now :)

    → Reply