FunctionRacerProblemsRace

Cheapest Order of Cuts

HardDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems