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:
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.
Examples:
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 rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20. Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 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 cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.
Constraints
2 <= n <= 106
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
All the integers in cuts array are distinct.
Time Complexity:
Time Complexity = O(m * n2)
Space Complexity:
Space Complexity = O(n2)
Approach
- We want to find the minimum cost to cut a stick of length n at given positions in cuts.
- Each
time we make a cut inside a segment (start, end), the cost of that cut is the current segment length (end - start). - After cutting at position c, the stick splits into two smaller segments:
- Left segment →
(start, c) - Right segment →
(c, end)
- Left segment →
- Use DFS recursion to try every possible cut c that lies between start and end.
- For each valid cut:
- Compute
currCost = (end - start) + dfs(start, c) + dfs(c, end) - Keep the
minimum costamong all choices.
- Compute
- Use a Map (dp) for memoization with key
"start_end"to store the minimum cost for each segment so that the same subproblem is not recomputed. - If no cut exists inside the segment, the cost is
0. - Start the recursion with the whole stick:
dfs(0, n).
Dry Run
Input: n = 7, cuts = [1, 3, 4, 5]
Goal:
We want the minimum cost to cut a stick of length 7.
Each cut costs the current stick length.
Call dfs(0, 7)
Step 1: dfs(0,7)
Possible cuts between 0 and 7 → [1,3,4,5]
Try cut = 1
Cost = (7 - 0) + dfs(0,1) + dfs(1,7)
dfs(0,1)
No cuts between 0 and 1
→ return 0
dfs(1,7)
Possible cuts → [3,4,5]
Try cut = 3
Cost = (7 - 1) + dfs(1,3) + dfs(3,7)
dfs(1,3)
No cuts inside
→ return 0
dfs(3,7)
Possible cuts → [4,5]
Try cut = 4
Cost = (7 - 3) + dfs(3,4) + dfs(4,7)
dfs(3,4) → 0
dfs(4,7)
Possible cut → [5]
Try cut = 5
Cost = (7 - 4) + dfs(4,5) + dfs(5,7)
= 3 + 0 + 0
= 3
→ dfs(4,7) = 3
Total cost = 4 + 0 + 3 = 7
Try cut = 5
Cost = (7 - 3) + dfs(3,5) + dfs(5,7)
dfs(3,5)
Possible cut → [4]
Cost = (5 - 3) + dfs(3,4) + dfs(4,5)
= 2 + 0 + 0
= 2
dfs(5,7) → 0
Total cost = 4 + 2 + 0 = 6
Minimum = 6
→ dfs(3,7) = 6
Total cost for cut=3
= 6 + 0 + 6
= 12
Continue checking other first cuts (3,4,5) similarly.
Minimum cost among all choices becomes:
→ 16
Memoization stores results for intervals like:
(0,7), (1,7), (3,7), (4,7), (3,5) etc.
Output: 16
var minCost = function(n, cuts) {
let dp = new Map();
let dfs = (start, end) => {
if(start >= end) return 0;
let key = start + "_" + end;
if(dp.has(key)) return dp.get(key);
let minCost = Infinity;
for(let c of cuts) {
if(c > start && c < end) {
let currCost = (end - start) +
dfs(start, c) + dfs(c, end);
minCost = Math.min(minCost, currCost)
}
}
minCost = minCost == Infinity ? 0 : minCost;
dp.set(key, minCost);
return minCost;
}
return dfs(0, n);
};
def minCost(n, cuts):
dp = {}
def dfs(start, end):
if start >= end:
return 0
key = (start, end)
if key in dp:
return dp[key]
min_cost = float('inf')
for c in cuts:
if start < c < end:
curr_cost = (end - start) + dfs(start, c) + dfs(c, end)
min_cost = min(min_cost, curr_cost)
if min_cost == float('inf'):
min_cost = 0
dp[key] = min_cost
return min_cost
return dfs(0, n)
import java.util.*;
class Solution {
Map dp = new HashMap<>();
public int minCost(int n, int[] cuts) {
return dfs(0, n, cuts);
}
private int dfs(int start, int end, int[] cuts) {
if(start >= end) return 0;
String key = start + "_" + end;
if(dp.containsKey(key)) return dp.get(key);
int minCost = Integer.MAX_VALUE;
for(int c : cuts) {
if(c > start && c < end) {
int currCost = (end - start) + dfs(start, c, cuts) + dfs(c, end, cuts);
minCost = Math.min(minCost, currCost);
}
}
if(minCost == Integer.MAX_VALUE) minCost = 0;
dp.put(key, minCost);
return minCost;
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
unordered_map dp;
int dfs(int start, int end, vector& cuts) {
if(start >= end) return 0;
string key = to_string(start) + "_" + to_string(end);
if(dp.count(key)) return dp[key];
int minCost = INT_MAX;
for(int c : cuts) {
if(c > start && c < end) {
int currCost = (end - start) + dfs(start, c, cuts) + dfs(c, end, cuts);
minCost = min(minCost, currCost);
}
}
if(minCost == INT_MAX) minCost = 0;
return dp[key] = minCost;
}
int minCost(int n, vector& cuts) {
return dfs(0, n, cuts);
}
};
#include <stdio.h>
#include <limits.h>
#include <string.h>
int dp[101][101];
int dfs(int start, int end, int cuts[], int size) {
if(start >= end) return 0;
if(dp[start][end] != -1) return dp[start][end];
int minCost = INT_MAX;
for(int i = 0; i < size; i++) {
int c = cuts[i];
if(c > start && c < end) {
int currCost = (end - start) +
dfs(start, c, cuts, size) +
dfs(c, end, cuts, size);
if(currCost < minCost)
minCost = currCost;
}
}
if(minCost == INT_MAX) minCost = 0;
return dp[start][end] = minCost;
}
int minCost(int n, int cuts[], int size) {
memset(dp, -1, sizeof(dp));
return dfs(0, n, cuts, size);
}
using System;
using System.Collections.Generic;
public class Solution {
Dictionary dp = new Dictionary();
public int MinCost(int n, int[] cuts) {
return dfs(0, n, cuts);
}
private int dfs(int start, int end, int[] cuts) {
if(start >= end) return 0;
string key = start + "_" + end;
if(dp.ContainsKey(key)) return dp[key];
int minCost = int.MaxValue;
foreach(int c in cuts) {
if(c > start && c < end) {
int currCost = (end - start) + dfs(start, c, cuts) + dfs(c, end, cuts);
minCost = Math.Min(minCost, currCost);
}
}
if(minCost == int.MaxValue) minCost = 0;
dp[key] = minCost;
return minCost;
}
}
