Minimum cost to cut the stick
HardInterval DP over the cut positions
Problem
Given a stick and cut positions, find the minimum total cost to make all cuts (a cut costs the current piece length).
Each cut costs the current piece's length; interval DP picks the order that minimises the total.
The idea
Add the stick's two ends to the cut list and sort it, then for each interval of cuts try every cut inside it first. The cost of a cut is the length of the piece being cut, which is the distance between the interval's endpoints.
The trick
- Pad the cuts with 0 and n, then sort.
- Cost of the current cut = cuts[j] - cuts[i], regardless of which cut you choose.
- O(m³) in the number of cuts.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — n=7, cuts=[1,3,4,5] Values: 1, 3, 4, 5.
1add 0 and n to cuts, sort2dp[i][j]=min over k of dp[i][k]+dp[k][j]+(cuts[j]-cuts[i])Input
- array
- [1, 3, 4, 5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 7, cuts = [1,3,4,5]
- Output:
- 16
- Explanation:
- Choosing a smart cut order costs 16.
Example 2
- Input:
- n = 9, cuts = [5,6,1,4,2]
- Output:
- 22
- Explanation:
- Best total cutting cost is 22.
Example 3
- Input:
- n = 4, cuts = [2]
- Output:
- 4
- Explanation:
- One cut costs the stick length 4.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.