#1547
Minimum Cost to Cut a Stick
Hard Partition DP (MCM style)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A stick of length n must be cut at given positions, in any order. Each cut costs the length of the piece being cut. Return the minimum total cost.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the cheapest order of cuts, where each cut costs the current piece length.
Why this works: interval DP over the sorted cut positions: dp[i][j] = piece length + the best first cut k inside.
Example: n = 7, cuts [1, 3, 4, 5]
cutting at 3 first, then 5, then 1 and 4 → 16✦Hints open one at a time
Sort the cuts and add 0 and n as boundaries.
dp[i][j] = cheapest way to make all cuts strictly between boundary i and boundary j.
Try each cut k in between as the first one: cost = (pos[j] − pos[i]) + dp[i][k] + dp[k][j].
↗Approach
Same shape as matrix chain multiplication. Fill by increasing gap between i and j.
</>Solution (Java)
import java.util.*;
class Solution {
public int minCost(int n, int[] cuts) {
int m = cuts.length + 2;
int[] pos = new int[m];
for (int i = 0; i < cuts.length; i++) pos[i + 1] = cuts[i];
pos[m - 1] = n;
Arrays.sort(pos);
int[][] dp = new int[m][m];
for (int gap = 2; gap < m; gap++) {
for (int i = 0; i + gap < m; i++) {
int j = i + gap;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++) { // first cut inside (i, j)
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
}
dp[i][j] += pos[j] - pos[i]; // that cut costs the piece length
}
}
return dp[0][m - 1];
}
}!Common mistake
Building the DP over the stick length n (up to 10^6) instead of over the cut positions.
Complexity
- Time: O(m³), m = number of cuts.
- Space: O(m²).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon