FunctionRacerProblemsRace

Ribbon for Sale

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

A ribbon is len(prices) centimeters long, and a buyer pays prices[k - 1] for a piece exactly k centimeters long. You may cut the ribbon into whole-centimeter pieces, but every cut costs fee. Selling it whole needs no cut.

Return the largest amount you can make: the prices of all the pieces you sell minus the fees for the cuts you made.

Example 1

prices [1,5,8,9]
fee 0
returns 10

Cut once into two 2 cm pieces: 5 + 5 = 10. Selling it whole gives only 9.

Example 2

prices [3,5,8,9]
fee 2
returns 9

Four 1 cm pieces bring 12 but need three cuts costing 6. Selling it whole gives 9, and so does one cut into 1 cm and 3 cm (3 + 8 - 2).

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