Leetcode problem:- Minimum cost to merge stones.

Правка en1, от rr459595, 2019-05-31 23:29:52

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][mid][x]+dp[mid+1][j][m-x]) for x in range(1,m-1) ?

Thanks.

Теги #dynamic-programming, leetcode

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский rr459595 2019-06-01 10:36:37 12 Tiny change: 'min(dp[i][mid]' -> 'min(dp[i][j][m],dp[i][mid]'
en2 Английский rr459595 2019-05-31 23:30:51 1 Tiny change: 'ge-stones/).\n\nThe ' -> 'ge-stones/ ).\n\nThe '
en1 Английский rr459595 2019-05-31 23:29:52 803 Initial revision (published)