Minimum Cost to Cut a Stick
Mastery
A stick of length length must be cut at the positions in cuts, in any order you choose. The cost of one cut is the current length of the piece being cut. Return the smallest total cost.
For length = 7 and cuts = [1, 3, 4, 5] the answer is 16 (cut at 3, then 5, then 1, then 4: costs 7 + 4 + 3 + 2).
The starter code tries every order of the cuts. It is correct but too slow for many cuts.
Examples
Example 1
Input:
min_cost_cut(7, [1, 3, 4, 5])
Output:
16
Example 2
Input:
min_cost_cut(9, [5, 6, 1, 4, 2])
Output:
22
Constraints
2 <= length <= 10000000 <= len(cuts) <= 1001 <= cut < length, all different
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingintervals-and-states
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.