Ribbon for Sale
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
1 <= len(prices) <= 1000 <= prices[i] <= 10000 <= fee <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Three Step StairsEasy
- Tiling a Two by N StripEasy
- Token Orders at the TurnstileEasy
- Two-Lane RoadEasy
- Best Stretch SumMedium
- Cheapest DescentMedium
- Cheapest Pool PassesMedium
- Coins From Either EndMedium