258. Minimum Cost to Cut a Stick
🔗 LeetCode Problem: 1547. Minimum Cost to Cut a Stick
📊 Difficulty: Hard
🏷️ Topics: Array, Dynamic Programming, Sorting
Problem Statement
Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:
0 ─────────────────────── 6
Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.
You should perform the cuts in order, you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.
Return the minimum total cost of the cuts.
Example 1:
Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:
The first cut is done to a stick of length 7 so the cost is 7.
The second cut is done to a stick of length 6 (from 0 to 6), the third is done to a stick of length 4 (from 3 to 7) and the last cut is done to a stick of length 3 (from 5 to 7).
The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] leads to:
First cut at 3 costs 7.
Second cut at 5 costs 4 (stick from 3 to 7).
Third cut at 1 costs 3 (stick from 0 to 3).
Fourth cut at 4 costs 2 (stick from 3 to 5).
Total cost = 7 + 4 + 3 + 2 = 16.
Example 2:
Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering, the total cost = 25.
There are many other orderings with total cost <= 25.
For example, [4,6,5,2,1] has total cost = 22 which is the minimum.
Constraints:
- 2 <= n <= 10^6
- 1 <= cuts.length <= min(n - 1, 100)
- 1 <= cuts[i] <= n - 1
- All the integers in cuts array are distinct.
🌳 Visual Understanding - The Stick Cutting Problem
Let's Discover This Problem Step by Step:
What are we doing?
Given: Stick of length 7, cuts at [1,3,4,5]
Goal: Cut at all positions with minimum total cost
Rule: Cost of cut = length of current stick piece
Stick: 0 ───────────────── 7
Cuts needed at: 1, 3, 4, 5
Key insight: ORDER MATTERS!
Different cut orders give different total costs!
Visual Discovery - Example 1:
n = 7, cuts = [1,3,4,5]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Strategy 1: Cut in given order [1,3,4,5]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initial: 0 ───────────────── 7 (length = 7)
Cut at 1:
0 ─ 1 ────────────── 7
Cost: 7 (full stick)
Pieces: [0,1] and [1,7]
Cut at 3 (in piece [1,7]):
0 ─ 1 ─── 3 ──── 7
Cost: 6 (length of [1,7])
Pieces: [0,1], [1,3], [3,7]
Cut at 4 (in piece [3,7]):
0 ─ 1 ─── 3 ─ 4 ─ 7
Cost: 4 (length of [3,7])
Pieces: [0,1], [1,3], [3,4], [4,7]
Cut at 5 (in piece [4,7]):
0 ─ 1 ─── 3 ─ 4 ─ 5 ─ 7
Cost: 3 (length of [4,7])
Final pieces: [0,1], [1,3], [3,4], [4,5], [5,7]
Total cost: 7 + 6 + 4 + 3 = 20
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Strategy 2: Cut in order [3,5,1,4]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initial: 0 ───────────────── 7 (length = 7)
Cut at 3:
0 ─────── 3 ──── 7
Cost: 7
Pieces: [0,3], [3,7]
Cut at 5 (in piece [3,7]):
0 ─────── 3 ─ 5 ─ 7
Cost: 4 (length of [3,7])
Pieces: [0,3], [3,5], [5,7]
Cut at 1 (in piece [0,3]):
0 ─ 1 ─── 3 ─ 5 ─ 7
Cost: 3 (length of [0,3])
Pieces: [0,1], [1,3], [3,5], [5,7]
Cut at 4 (in piece [3,5]):
0 ─ 1 ─── 3 ─ 4 ─ 5 ─ 7
Cost: 2 (length of [3,5])
Final pieces: [0,1], [1,3], [3,4], [4,5], [5,7]
Total cost: 7 + 4 + 3 + 2 = 16 ✓ BETTER!
Different order = different cost!
We need DP to find optimal order! 🔑
The Key Insight:
This is similar to Matrix Chain Multiplication!
Key observation:
When we cut a stick [left, right] at position mid,
the cost is (right - left)
Then we need to recursively cut:
- Left piece: [left, mid]
- Right piece: [mid, right]
This is INTERVAL DP!
But there's a trick: We need to SORT the cuts first!
Why? Because the cuts positions matter, not their order! 🎯
🧠 Discovering the Solution - Building Intuition
Let's Think Through This:
Question 1: Why is this a DP problem?
Optimal Substructure:
minCost(stick[left..right]) with cuts in between
= cost of first cut + minCost(left piece) + minCost(right piece)
Try all possible first cuts, take minimum!
Overlapping Subproblems:
Different cut orders lead to same sub-sticks
Example: After cutting at 3 and 5, we have stick [3,5]
This appears multiple times!
This is DP! And specifically, interval DP!
Question 2: Why sort the cuts array?
Original cuts: [1,3,4,5]
After sorting: [1,3,4,5] (already sorted)
Why sort?
The POSITIONS matter, not the INPUT order!
We need to know:
"Which cuts are between left and right?"
Sorting allows us to efficiently find cuts in range!
Also add boundaries:
cuts = [0, 1, 3, 4, 5, 7]
Now cuts[0]=0 and cuts[m-1]=7 represent stick ends!
Question 3: What's the DP state?
dp[i][j] = minimum cost to cut stick from cuts[i] to cuts[j]
with all cuts between i and j
Example:
dp[0][5] = min cost to cut entire stick [0,7]
with cuts at 1,3,4,5
dp[1][3] = min cost to cut stick [1,4]
with cuts at 3
Question 4: What's the recurrence?
For stick [cuts[i], cuts[j]] with cuts at positions i+1, i+2, ..., j-1:
Try each cut position k where i < k < j:
Cost of cutting at cuts[k]:
= (cuts[j] - cuts[i]) // length of stick
+ dp[i][k] // cost of left piece
+ dp[k][j] // cost of right piece
Take minimum over all k!
dp[i][j] = min(cuts[j] - cuts[i] + dp[i][k] + dp[k][j])
for all i < k < j
Base case:
dp[i][i+1] = 0 (no cuts between adjacent positions)
🟢 Approach 1: Brute Force Recursion
💡 Intuition
Try all possible orders of cuts:
- For each stick segment, try each cut position
- Recursively solve for resulting pieces
- Take minimum cost
Start with pure recursion to understand structure!
📝 Implementation
class Solution {
public int minCost(int n, int[] cuts) {
// Add boundaries and sort
int m = cuts.length;
int[] newCuts = new int[m + 2];
newCuts[0] = 0;
newCuts[m + 1] = n;
System.arraycopy(cuts, 0, newCuts, 1, m);
Arrays.sort(newCuts);
return minCostRecursive(newCuts, 0, m + 1);
}
private int minCostRecursive(int[] cuts, int left, int right) {
// Base case: no cuts between left and right
if (right - left <= 1) {
return 0;
}
int minCost = Integer.MAX_VALUE;
// Try each cut position between left and right
for (int k = left + 1; k < right; k++) {
// Cost of cutting at position cuts[k]
int cost = (cuts[right] - cuts[left]) // current stick length
+ minCostRecursive(cuts, left, k) // left piece
+ minCostRecursive(cuts, k, right); // right piece
minCost = Math.min(minCost, cost);
}
return minCost;
}
}
🔍 Dry Run - Example: n = 7, cuts = [1,3,4,5]
Input: n = 7, cuts = [1,3,4,5]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Prepare cuts array
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Original: [1,3,4,5]
Add boundaries: [0,1,3,4,5,7]
After sort: [0,1,3,4,5,7]
Indices: 0 1 2 3 4 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Recursion Tree (key paths)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
minCostRecursive(cuts, 0, 5): // Stick [0,7]
Cuts available: 1,3,4,5 (indices 1,2,3,4)
Try k=1: Cut at position 1
Cost = (7-0) + rec(0,1) + rec(1,5)
= 7 + 0 + rec(1,5)
rec(1,5): // Stick [1,7]
Try k=2: Cut at position 3
Cost = (7-1) + rec(1,2) + rec(2,5)
= 6 + 0 + rec(2,5)
rec(2,5): // Stick [3,7]
Try k=3: Cut at position 4
Cost = (7-3) + rec(2,3) + rec(3,5)
= 4 + 0 + rec(3,5)
rec(3,5): // Stick [4,7]
Try k=4: Cut at position 5
Cost = (7-4) + rec(3,4) + rec(4,5)
= 3 + 0 + 0
= 3
return 3
Cost = 4 + 0 + 3 = 7
return 7
Cost = 6 + 0 + 7 = 13
return 13
Cost = 7 + 0 + 13 = 20
Try k=2: Cut at position 3
Cost = (7-0) + rec(0,2) + rec(2,5)
= 7 + rec(0,2) + rec(2,5)
rec(0,2): // Stick [0,3]
Try k=1: Cut at 1
Cost = (3-0) + 0 + 0 = 3
return 3
rec(2,5) = 7 (computed above)
Cost = 7 + 3 + 7 = 17
Try k=3: Cut at position 4
Cost = 7 + rec(0,3) + rec(3,5)
rec(0,3): // Stick [0,4]
... computation ...
return 7
rec(3,5) = 3
Cost = 7 + 7 + 3 = 17
Try k=4: Cut at position 5
Cost = 7 + rec(0,4) + rec(4,5)
= 7 + 10 + 0 = 17
return min(20, 17, 17, 17) = 17
Wait, expected answer is 16! Let me trace k=2 more carefully...
Actually, let me recalculate rec(2,5):
Try k=4: Cut at 5 first
Cost = 4 + rec(2,4) + rec(4,5)
rec(2,4): try k=3, cost = 2+0+0 = 2
Cost = 4 + 2 + 0 = 6 ✓
return 6
So total for k=2: 7 + 3 + 6 = 16 ✓
Answer: 16
📊 Complexity Analysis
Time Complexity: Exponential
Without memoization, many repeated subproblems
Each position can be cut first
Exponential branching
Space Complexity: O(m)
Recursion stack depth
m = number of cuts
🟡 Approach 2: Top-Down DP (Memoization)
💡 Intuition
Same recursive structure, but cache results!
Key: dp[left][right] computed once and reused
Dramatically reduces repeated computation!
📝 Implementation
class Solution {
public int minCost(int n, int[] cuts) {
// Add boundaries and sort
int m = cuts.length;
int[] newCuts = new int[m + 2];
newCuts[0] = 0;
newCuts[m + 1] = n;
System.arraycopy(cuts, 0, newCuts, 1, m);
Arrays.sort(newCuts);
// Memoization table
Integer[][] memo = new Integer[m + 2][m + 2];
return minCostMemo(newCuts, 0, m + 1, memo);
}
private int minCostMemo(int[] cuts, int left, int right, Integer[][] memo) {
// Base case
if (right - left <= 1) {
return 0;
}
// Check memo
if (memo[left][right] != null) {
return memo[left][right];
}
int minCost = Integer.MAX_VALUE;
// Try each cut position
for (int k = left + 1; k < right; k++) {
int cost = (cuts[right] - cuts[left])
+ minCostMemo(cuts, left, k, memo)
+ minCostMemo(cuts, k, right, memo);
minCost = Math.min(minCost, cost);
}
memo[left][right] = minCost;
return minCost;
}
}
📊 Complexity Analysis
Time Complexity: O(m³)
States: O(m²) for all [left, right] pairs
Each state: O(m) to try all cut positions
Total: O(m³)
Space Complexity: O(m²)
Memoization table: m × m
Recursion stack: O(m)
Total: O(m²)
🟢 Approach 3: Bottom-Up DP (Tabulation)
💡 Intuition
Build solution iteratively!
Process intervals by increasing length
For each interval, try all cut positions
No recursion needed!
📝 Implementation
class Solution {
public int minCost(int n, int[] cuts) {
// Add boundaries and sort
int m = cuts.length;
int[] newCuts = new int[m + 2];
newCuts[0] = 0;
newCuts[m + 1] = n;
System.arraycopy(cuts, 0, newCuts, 1, m);
Arrays.sort(newCuts);
// DP table: dp[i][j] = min cost to cut stick [cuts[i], cuts[j]]
int[][] dp = new int[m + 2][m + 2];
// Process by interval length
for (int len = 2; len <= m + 1; len++) {
for (int left = 0; left + len <= m + 1; left++) {
int right = left + len;
dp[left][right] = Integer.MAX_VALUE;
// Try each cut position between left and right
for (int k = left + 1; k < right; k++) {
int cost = (newCuts[right] - newCuts[left])
+ dp[left][k]
+ dp[k][right];
dp[left][right] = Math.min(dp[left][right], cost);
}
}
}
return dp[0][m + 1];
}
}
🔍 Complete Dry Run - Example: n = 7, cuts = [3,5,1,4]
Input: n = 7, cuts = [3,5,1,4]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Prepare cuts array
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Original: [3,5,1,4]
Add boundaries: [0,3,5,1,4,7]
After sort: [0,1,3,4,5,7]
Indices: 0 1 2 3 4 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initialize DP table
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[i][i+1] = 0 for all i (no cuts between adjacent positions)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Length 2 (intervals of 2)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
All dp[i][i+1] = 0 (already initialized)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Length 3 (intervals with 1 cut inside)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][2]: Stick [0,3], cut at 1
k=1: cost = (3-0) + dp[0][1] + dp[1][2]
= 3 + 0 + 0 = 3
dp[0][2] = 3
dp[1][3]: Stick [1,4], cut at 3
k=2: cost = (4-1) + dp[1][2] + dp[2][3]
= 3 + 0 + 0 = 3
dp[1][3] = 3
dp[2][4]: Stick [3,5], cut at 4
k=3: cost = (5-3) + dp[2][3] + dp[3][4]
= 2 + 0 + 0 = 2
dp[2][4] = 2
dp[3][5]: Stick [4,7], cut at 5
k=4: cost = (7-4) + dp[3][4] + dp[4][5]
= 3 + 0 + 0 = 3
dp[3][5] = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Length 4 (intervals with 2 cuts inside)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][3]: Stick [0,4], cuts at 1,3
Try k=1: (4-0) + dp[0][1] + dp[1][3]
= 4 + 0 + 3 = 7
Try k=2: (4-0) + dp[0][2] + dp[2][3]
= 4 + 3 + 0 = 7
dp[0][3] = min(7, 7) = 7
dp[1][4]: Stick [1,5], cuts at 3,4
Try k=2: (5-1) + dp[1][2] + dp[2][4]
= 4 + 0 + 2 = 6
Try k=3: (5-1) + dp[1][3] + dp[3][4]
= 4 + 3 + 0 = 7
dp[1][4] = min(6, 7) = 6
dp[2][5]: Stick [3,7], cuts at 4,5
Try k=3: (7-3) + dp[2][3] + dp[3][5]
= 4 + 0 + 3 = 7
Try k=4: (7-3) + dp[2][4] + dp[4][5]
= 4 + 2 + 0 = 6
dp[2][5] = min(7, 6) = 6
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Length 5 (intervals with 3 cuts inside)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][4]: Stick [0,5], cuts at 1,3,4
Try k=1: (5-0) + dp[0][1] + dp[1][4]
= 5 + 0 + 6 = 11
Try k=2: (5-0) + dp[0][2] + dp[2][4]
= 5 + 3 + 2 = 10
Try k=3: (5-0) + dp[0][3] + dp[3][4]
= 5 + 7 + 0 = 12
dp[0][4] = min(11, 10, 12) = 10
dp[1][5]: Stick [1,7], cuts at 3,4,5
Try k=2: (7-1) + dp[1][2] + dp[2][5]
= 6 + 0 + 6 = 12
Try k=3: (7-1) + dp[1][3] + dp[3][5]
= 6 + 3 + 3 = 12
Try k=4: (7-1) + dp[1][4] + dp[4][5]
= 6 + 6 + 0 = 12
dp[1][5] = 12
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Length 6 (full stick with all 4 cuts)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][5]: Stick [0,7], cuts at 1,3,4,5
Try k=1: (7-0) + dp[0][1] + dp[1][5]
= 7 + 0 + 12 = 19
Try k=2: (7-0) + dp[0][2] + dp[2][5]
= 7 + 3 + 6 = 16 ✓
Try k=3: (7-0) + dp[0][3] + dp[3][5]
= 7 + 7 + 3 = 17
Try k=4: (7-0) + dp[0][4] + dp[4][5]
= 7 + 10 + 0 = 17
dp[0][5] = min(19, 16, 17, 17) = 16
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][5] = 16 ✓
Optimal cutting order (from k=2):
Cut at position 3 first (cost 7)
Left [0,3]: cut at 1 (cost 3)
Right [3,7]: cut at 5, then 4 (cost 6)
Total: 7 + 3 + 6 = 16
📊 Complexity Analysis
Time Complexity: O(m³)
Three nested loops:
- Length: O(m)
- Left position: O(m)
- Cut position k: O(m)
Total: O(m³)
Space Complexity: O(m²)
DP table: (m+2) × (m+2)
Total: O(m²)
🟢 Approach 4: Space Optimization Discussion
💡 Analysis
Can we reduce space from O(m²)?
Observation: dp[left][right] depends on:
- dp[left][k] for all k < right
- dp[k][right] for all k > left
These are "smaller" intervals, but not in a simple pattern
For interval DP like this:
- Need entire 2D table
- Can't reduce to 1D easily
- O(m²) space is optimal
Unlike linear DP where we can use rolling arrays,
interval DP requires the full matrix!
🎯 Key Insights Summary
The Five Critical Points:
1. Sort the Cuts Array First
MUST sort after adding boundaries!
cuts = [3,5,1,4]
→ [0,1,3,4,5,7]
Why?
- Need to know which cuts are in range [i,j]
- Sorting makes interval DP work
- Positions matter, not input order! 🔑
2. Add Boundaries (0 and n)
Original cuts: [1,3,4,5]
With boundaries: [0,1,3,4,5,7]
Why?
- Represent stick endpoints
- Simplifies DP logic
- dp[0][m+1] = answer for full stick
3. Interval DP Pattern
dp[i][j] = min cost for stick [cuts[i], cuts[j]]
Process by increasing interval length!
- Length 2: Adjacent positions (base case)
- Length 3: One cut inside
- ...
- Length m+1: Full stick
This is classic interval DP! 🎯
4. Try All Cut Positions
For interval [i,j]:
Try cutting at each k where i < k < j
Cost = (cuts[j] - cuts[i]) // stick length
+ dp[i][k] // left piece
+ dp[k][j] // right piece
Take minimum!
5. Similar to Matrix Chain Multiplication
Both problems:
- Interval DP
- Try all split points
- Combine subproblem costs
Pattern recognition helps! ✓
📝 Quick Revision Notes
🎯 Core Concept
Problem: Cut stick at all positions with minimum total cost
Key Trick: Sort cuts array after adding boundaries!
DP State:
dp[i][j] = min cost to cut stick [cuts[i], cuts[j]]
with all cuts between i and j
Recurrence:
dp[i][j] = min(cuts[j] - cuts[i] + dp[i][k] + dp[k][j])
for all i < k < j
Base Case:
dp[i][i+1] = 0 (no cuts between adjacent positions)
🎪 Memory Aid
"Sort the cuts, add boundaries first!"
"Interval DP, length disperse!"
"Try all k, costs immersed!"
"Minimum sum, optimal burst!" ✨
🎉 Congratulations!
You've mastered Minimum Cost to Cut a Stick!
What You Learned:
✅ Interval DP - Process by increasing length
✅ Sorting trick - Sort cuts with boundaries
✅ Optimal substructure - Try all split points
✅ Matrix Chain pattern - Similar structure
✅ Hard problem - O(m³) solution
This problem is a classic application of interval DP with the clever twist of sorting! The pattern appears in many optimization problems! 🚀✨🎯