1547.. leetcode problem...minimum cost to cut a stick

#1

Sir, I m facing problem in 1547 leetcode problem minimum cost to sut a stick.
this is my code:

All sample cases are passing but having problem in following case:
36
[13,17,15,18,3,22,27,6,35,7,11,28,26,20,4,5,21,10,8]

my output:156
expected: 150

basically, i m trying to join the stick after it has been cut from all its cuts length.
plss check…

#2

plss respond…

#3

Hey @aman17nov1999, I believe you’re approaching the question incorrectly. This is a variation of a classical dynamic programming question.
Let dp[i][j] be the minimum cost if we cut on stick from A[i] to A[j]
(note here the order matters so we can’t simply sort it).

  • If j == i + 1 ( len == 2 ), we can’t cut on this stick, so dp[i][j] = 0 .
  • If j == i + 2 ( len == 3 ), the only choice you have is to cut in the middle, and the cost is the length of this stick, so dp[i][j] = A[i + 2] - A[i] .
  • If j > i + 2 ( len >= 4 ), we can try to cut at k where i < k < j and use the minimum cost we can get which is the cost of cutting the left part dp[i][k] plus the cost of cutting the right part dp[k][j] and the cost of the current cut A[j] - A[i] , so dp[i][j] = min( dp[i][k] + dp[k][j] + A[j] - A[i] | i < k < j)

The answer is dp[0][N-1] .