DSA problem
Minimum Cost to Cut a Stick
Given a stick of length n and a list of integer cuts indicating positions where you must cut the stick (0 < cuts[i] < n), determine the minimum total cost to perform all the cuts. The cost of a cut equals the current length of the stick segment being cut, and after a cut the segment splits into two. You may perform the cuts in any order.
The order in which you perform cuts matters: cutting at a position high up the chain divides the work into halves and recursively each half's cuts cost only the length of that sub-stick. A different ordering may pay long lengths multiple times. The optimum is found by interval DP.
Augment the cuts array by adding 0 at the start and n at the end and then sort it. The sorted sequence c[0..k - 1] (k = len(cuts) + 2) represents the cut positions plus the two stick endpoints. Define dp[i][j] (i < j - 1) = minimum cost to perform every cut strictly between c[i] and c[j] on a sub-stick whose endpoints are at those positions. The cost of making the first cut at any k in (i, j) is the length of the current sub-stick c[j] - c[i] plus the costs of the two resulting sub-problems.
So dp[i][j] = (c[j] - c[i]) + min over k in (i, j) of (dp[i][k] + dp[k][j]). Base case: dp[i][i + 1] = 0 (no cut between adjacent positions). Fill by ascending range length. The answer is dp[0][k - 1]. Time O(k^3), space O(k^2).
Examples
n = 7, cuts = [1,3,4,5]16n = 9, cuts = [5,6,1,4,2]22n = 10, cuts = [3]10Constraints
- 2 <= n <= 10^6
- 1 <= cuts.length <= min(n - 1, 100)
- 1 <= cuts[i] <= n - 1
- All elements of `cuts` are unique.
- A single cut's cost equals the current length of the stick being cut.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.