Leetcode Problem 1547. Minimum Cost to Cut a Stick

1547. Minimum Cost to Cut a Stick

Leetcode Solutions

Bottom-up Dynamic Programming Approach

  1. Sort the array cuts and add 0 and n to the beginning and end of the array respectively.
  2. Initialize a 2D array dp of size (m+2) x (m+2) with all elements set to 0, where m is the number of cuts.
  3. Iterate over the length of subproblems l from 2 to m+1 (inclusive).
  4. For each subproblem length l, iterate over all possible starting points i for the subproblem.
  5. Set the ending point j of the subproblem to i + l.
  6. Initialize dp[i][j] to infinity.
  7. Iterate over all possible positions k for the next cut between i and j.
  8. Update dp[i][j] to the minimum of its current value and the sum of dp[i][k], dp[k][j], and the cost of making the cut at position k.
  9. After filling the dp table, return dp[0][m+1] as the answer.
UML Thumbnail

Top-down Dynamic Programming Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...