Cheapest Order of Cuts
A plank is length long. It has to be sawn at every position listed in cuts, measured from its left end, and you choose the order of the cuts. A cut costs the length of the piece it is made in at that moment.
Return the least total cost of making all the cuts.
Example 1
length 10
cuts [2,7]
returns 17
Cut at 7 first, which costs 10. The cut at 2 is then made in a piece of length 7. The other order costs 10 + 8.
Example 2
length 5
cuts [3]
returns 5
One cut through the whole plank.
Constraints
2 <= length <= 10**61 <= len(cuts) <= 401 <= cuts[i] <= length - 1, all different
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.