Cheapest Order to Cut a Rod
Problem statement
A wooden rod has length n, with marks at positions 0 to n. You must cut it at every position listed in cuts, one cut at a time, in any order you like.
A cut always splits one piece into two, and it costs the length of the piece being cut at that moment. For example, the first cut always costs n.
Return the smallest possible total cost of making all the cuts.
Function
minCutCost(n: int, cuts: int[]) → intExamples
Example 1
n = 10cuts = [2,7,8]return = 20Cut at 7 first (cost 10), leaving pieces 0-7 and 7-10. Then cut 0-7 at 2 (cost 7) and 7-10 at 8 (cost 3). The total is 10 + 7 + 3 = 20. Cutting at 2 first would cost 10 + 8 + 6 = 24 or 10 + 8 + 3 = 21 at best.
Example 2
n = 5cuts = [3]return = 5One cut on a rod of length 5 always costs 5.
Example 3
n = 12cuts = [1,2,3,9,10,11]return = 31Cut at 3 and 9 first to split off the two crowded ends: 12 + 9 = 21. Each end piece of length 3 then needs two cuts costing 3 + 2 = 5, so the total is 21 + 5 + 5 = 31.
Constraints
2 <= n <= 10^61 <= cuts.length <= min(n - 1, 100)1 <= cuts[i] <= n - 1, and all values incutsare different