DiffPush Tier Dynamic Programming · DP on Partition O(m^3) · O(m^2)
A stone workshop must slice a marble slab at a list of marked positions. Each pass of the saw bills the current length of the piece being cut, and the foreman may execute the marks in any order. Scheduling smartly — cutting expensive pieces apart early — can slash the invoice, so the shop wants the cheapest total billing plan.
Input: An integer n (stick length) and an array cuts of distinct cut positions.
Output: Return the minimum total cost to perform all cuts, where each cut costs the length of the piece cut.
2 <= n <= 10^61 <= len(cuts) <= min(n - 1, 100)1 <= cuts[i] <= n - 1all cut positions are distinctInput: {"n":7,"cuts":[1,3,4,5]}
Output: 16
Cutting 1, then 5, then 3, then 4 keeps every billed length small — total 16.
Input: {"n":9,"cuts":[5,6,1,4,2]}
Output: 22
Order 2, 1, 4, 5, 6 achieves the minimum billing of 22.