Minimum Cost to Cut a Stick solution and explanation
Google
9 more videos on this problem
Minimum Cost to Cut a Stick - Leetcode 1547 - PythonNeetCodeIO · 12:15 · 22K views
Minimum Cost to Cut a Stick | Recur + Memo | Time Complexity | GOOGLE | Leetcode-1547 | Live CodecodestorywithMIK · 38:27 · 18K views
1547. Minimum Cost to Cut a Stick | Leetcode | Weekly Contest 201Roshan Srivastava · 18:56 · 9K views
Minimum Cost to Cut a Stick || Merge Stones || Burst Ballons || Dynamic Programming || Leetcode 1547Aryan Mittal · 23:10 · 8K views
LeetCode 1547. Minimum Cost to Cut a StickHappy Coding · 14:09 · 5K views
LEETCODE 1547. Minimum Cost to Cut a Stick | Understand the approach (DETAILED EXPLANATION)Abrar Sher · 24:09 · 5K views
1547. Minimum Cost to Cut a Stick | DYNAMIC PROGRAMMING | LEETCODE HARDcode Explainer · 12:00 · 4K views
1547. Minimum Cost to Cut a Stick (Leetcode Hard)Programming Live with Larry · 7:53 · 2K views
1547. Minimum Cost to Cut a Stick | DP | LeetCode Daily ChallengeDeep Tech · 16:39 · 1K views
DP 50. Minimum Cost to Cut the Sticktake U forward · 30:02 · 250K views
The problem
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.
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 <= 1061 <= cuts.length <= min(n - 1, 100)1 <= cuts[i] <= n - 1- All the integers in
cutsarray are distinct.
Approach overview
Problem Overview: You have a stick of length n and a list of positions where cuts must be made. Each cut costs the current length of the stick segment being cut. The goal is to determine the order of cuts that minimizes the total cost.
Approach 1: Recursive with Memoization (Interval DP) (Time: O(m^3), Space: O(m^2))
The key observation is that every cut splits the stick into two independent subproblems. First sort the cuts array and add boundaries 0 and n. When you choose a cut k between positions i and j, the cost is the current segment length cuts[j] - cuts[i], plus the minimum cost to cut the left segment and the right segment. Use recursion to try every possible middle cut and store results in a memo table keyed by (i, j). This avoids recomputing overlapping subproblems and turns an exponential search into a manageable dynamic programming solution. The approach relies on sorted positions from sorting and interval subproblems typical in dynamic programming.
Approach 2: Bottom-Up Dynamic Programming (Interval DP) (Time: O(m^3), Space: O(m^2))
The iterative version builds a DP table where dp[i][j] represents the minimum cost to cut the segment between cuts[i] and cuts[j]. After sorting the cuts and adding boundaries, iterate over segment lengths and compute values for increasing interval sizes. For each interval (i, j), try every possible cut k between them and update dp[i][j] with (cuts[j] - cuts[i]) + dp[i][k] + dp[k][j]. This systematic iteration guarantees that smaller intervals are solved before larger ones. The input itself is stored in an array, and the DP table captures optimal substructure across stick segments.
Recommended for interviews: Interviewers typically expect the interval dynamic programming solution. A naive recursive approach shows the correct intuition that each cut divides the problem, but it leads to exponential complexity. Adding memoization or converting to bottom‑up DP demonstrates strong understanding of overlapping subproblems and optimal substructure, which are core concepts in dynamic programming interview questions.
Approach 1: Dynamic Programming Approach
This method leverages dynamic programming to find the minimum cost by solving subproblems. We start by sorting the cuts to facilitate an easier partitioning strategy. Then, define a dp table where dp[i][j] represents the minimum cost to perform all the cuts between positions i and j.
Use the recursive relation to compute the minimum cost for each partition (i, j) by considering every possible cut position in that interval. The base case is that if there are no cuts between two positions, the cost is zero.
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts = sorted(cuts)
cuts = [0] + cuts + [n]
m = len(cuts)
dp = [[0] * m for _ in range(m)]
for length in range(2, m):
for i in range(m - length):
j = i + length
dp[i][j] = min(dp[i][k] + dp[k][j] for k in range(i + 1, j)) + cuts[j] - cuts[i]
return dp[0][m - 1]
# Example usage
sol = Solution()
cuts = [1, 3, 4, 5]
n = 7
print("Minimum cost:", sol.minCost(n, cuts))import java.util.*;
class Solution {
public int minCost(int n, int[] cuts) {
Arrays.sort(cuts);
int m = cuts.length;
int[] newCuts = new int[m + 2];
System.arraycopy(cuts, 0, newCuts, 1, m);
newCuts[0] = 0;
newCuts[m + 1] = n;
int[][] dp = new int[m + 2][m + 2];
for (int len = 2; len <= m + 1; ++len) {
for (int i = 0; i <= m + 1 - len; ++i) {
int j = i + len;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; ++k) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + newCuts[j] - newCuts[i]);
}
}
}
return dp[0][m + 1];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] cuts = {1, 3, 4, 5};
int n = 7;
System.out.println("Minimum cost: " + sol.minCost(n, cuts));
}
}#include <vector>
#include <algorithm>
#include <climits>
class Solution {
public:
int minCost(int n, std::vector<int>& cuts) {
cuts.push_back(0);
cuts.push_back(n);
std::sort(cuts.begin(), cuts.end());
int m = cuts.size();
std::vector<std::vector<int>> dp(m, std::vector<int>(m, 0));
for (int len = 2; len < m; ++len) {
for (int i = 0; i < m - len; ++i) {
int j = i + len;
dp[i][j] = INT_MAX;
for (int k = i + 1; k < j; ++k) {
dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i]);
}
}
}
return dp[0][m-1];
}
};
int main() {
Solution sol;
std::vector<int> cuts = {1, 3, 4, 5};
int n = 7;
int result = sol.minCost(n, cuts);
std::cout << "Minimum cost: " << result << std::endl;
return 0;
}const minCost = (n, cuts) => {
cuts.sort((a, b) => a - b);
cuts = [0, ...cuts, n];
const m = cuts.length;
const dp = Array.from({ length: m }, () => Array(m).fill(0));
for (let len = 2; len < m; ++len) {
for (let i = 0; i < m - len; ++i) {
const j = i + len;
dp[i][j] = Infinity;
for (let k = i + 1; k < j; ++k) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i]);
}
}
}
return dp[0][m - 1];
};
// Example usage
const n = 7;
const cuts = [1, 3, 4, 5];
console.log("Minimum cost:", minCost(n, cuts));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int minCost(int n, int* cuts, int cutsSize) {
qsort(cuts, cutsSize, sizeof(int), (int(*)(const void*, const void*))strcmp);
int* newCuts = (int*)malloc((cutsSize + 2) * sizeof(int));
newCuts[0] = 0; newCuts[cutsSize + 1] = n;
for (int i = 0; i < cutsSize; ++i) newCuts[i + 1] = cuts[i];
int** dp = (int**)malloc((cutsSize + 2) * sizeof(int*));
for (int i = 0; i < cutsSize + 2; ++i) {
dp[i] = (int*)malloc((cutsSize + 2) * sizeof(int));
for (int j = 0; j < cutsSize + 2; ++j) dp[i][j] = 0;
}
for (int len = 2; len <= cutsSize + 1; ++len) {
for (int i = 0; i <= cutsSize + 1 - len; ++i) {
int j = i + len;
dp[i][j] = INT_MAX;
for (int k = i + 1; k < j; ++k) {
dp[i][j] = fmin(dp[i][j], newCuts[j] - newCuts[i] + dp[i][k] + dp[k][j]);
}
}
}
int result = dp[0][cutsSize + 1];
for (int i = 0; i < cutsSize + 2; ++i) free(dp[i]);
free(dp);
free(newCuts);
return result;
}
int main() {
int cuts[] = {1, 3, 4, 5};
int n = 7;
printf("Minimum cost: %d\n", minCost(n, cuts, 4));
return 0;
}using System;
class Solution {
public int MinCost(int n, int[] cuts) {
Array.Sort(cuts);
int m = cuts.Length;
int[] newCuts = new int[m + 2];
Array.Copy(cuts, 0, newCuts, 1, m);
newCuts[0] = 0;
newCuts[m + 1] = n;
int[,] dp = new int[m + 2, m + 2];
for (int len = 2; len <= m + 1; len++) {
for (int i = 0; i <= m + 1 - len; i++) {
int j = i + len;
dp[i, j] = int.MaxValue;
for (int k = i + 1; k < j; k++) {
dp[i, j] = Math.Min(dp[i, j], newCuts[j] - newCuts[i] + dp[i, k] + dp[k, j]);
}
}
}
return dp[0, m + 1];
}
static void Main(string[] args) {
int[] cuts = { 1, 3, 4, 5 };
int n = 7;
Solution sol = new Solution();
Console.WriteLine("Minimum cost: " + sol.MinCost(n, cuts));
}
}In Python, a list 'cuts' is sorted, then prepared with boundaries to assist in calculating distinct cost measures over subproblems. It uses comprehension and a principal loop structure to fill 'dp' with the minimum obtainable costs for the cut sequences.
Time Complexity: O(m^3) due to nested operations over the list size.
Space Complexity: O(m^2) since we maintain a matrix proportional to the problem constraints.
Approach 2: Recursive with Memoization
This approach uses recursive function calls along with a memoization hash table to store the results of subproblem calculations. This reduces repeated calculations and enhances efficiency. Order the cuts, then define a recursive function that selects the appropriate cut division and employs the same function to solve newly formed partitions recursively.
from functools import lru_cache
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts = sorted(cuts)
cuts = [0] + cuts + [n]
@lru_cache(None)
def cost(left: int, right: int) -> int:
if right - left <= 1:
return 0
return min(
cuts[right] - cuts[left] + cost(left, mid) + cost(mid, right)
for mid in range(left + 1, right)
)
return cost(0, len(cuts) - 1)
# Example usage
solution = Solution()
cuts = [1, 3, 4, 5]
n = 7
print('Minimum cost:', solution.minCost(n, cuts))import java.util.*;
class Solution {
private HashMap<String, Integer> memo;
private int[] cuts;
public int minCost(int n, int[] cuts) {
Arrays.sort(cuts);
this.cuts = new int[cuts.length + 2];
System.arraycopy(cuts, 0, this.cuts, 1, cuts.length);
this.cuts[0] = 0;
this.cuts[this.cuts.length - 1] = n;
memo = new HashMap<>();
return cost(0, this.cuts.length - 1);
}
private int cost(int left, int right) {
if (right - left <= 1) return 0;
String key = left + "," + right;
if (memo.containsKey(key)) return memo.get(key);
int ans = Integer.MAX_VALUE;
for (int i = left + 1; i < right; i++)
ans = Math.min(ans, cuts[right] - cuts[left] + cost(left, i) + cost(i, right));
memo.put(key, ans);
return ans;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] cuts = {1, 3, 4, 5};
int n = 7;
System.out.println("Minimum cost: " + sol.minCost(n, cuts));
}
}This Python implementation exploits the 'lru_cache' decorator to memoize results of recursive 'cost' function calls, trim down redundant calculations, and obtain a minimum cost sequence quickly.
Time Complexity: O(m^2) with memoization staving off excessive recomputation.
Space Complexity: O(m^2) result-caching leading to rational storage expansion.
Approach 3: Dynamic Programming (Interval DP)
We can add two elements to the array cuts, namely 0 and n, representing the two ends of the stick. Then we sort the cuts array, so we can divide the entire stick into several intervals, each with two cut points. Let the length of the cuts array be m.
Next, we define f[i][j] to represent the minimum cost to cut the interval [cuts[i], cuts[j]].
If an interval has only two cut points, meaning we do not need to cut this interval, then f[i][j] = 0.
Otherwise, we enumerate the length l of the interval, where l is equal to the number of cut points minus 1. Then we enumerate the left endpoint i of the interval, and the right endpoint j can be obtained by i + l. For each interval, we enumerate its cut point k, where i \lt k \lt j. We can then divide the interval [i, j] into [i, k] and [k, j]. The cost at this point is f[i][k] + f[k][j] + cuts[j] - cuts[i]. We take the minimum value among all possible k, which is the value of f[i][j].
Finally, we return f[0][m - 1].
The time complexity is O(m^3), and the space complexity is O(m^2). Here, m is the length of the modified cuts array.
function minCost(n: number, cuts: number[]): number {
cuts.push(0, n);
cuts.sort((a, b) => a - b);
const m = cuts.length;
const f: number[][] = Array.from({ length: m }, () => Array(m).fill(0));
for (let l = 2; l < m; l++) {
for (let i = 0; i < m - l; i++) {
const j = i + l;
f[i][j] = Infinity;
for (let k = i + 1; k < j; k++) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]);
}
}
}
return f[0][m - 1];
}func minCost(n int, cuts []int) int {
cuts = append(cuts, []int{0, n}...)
sort.Ints(cuts)
m := len(cuts)
f := make([][]int, m)
for i := range f {
f[i] = make([]int, m)
}
for l := 2; l < m; l++ {
for i := 0; i+l < m; i++ {
j := i + l
f[i][j] = 1 << 30
for k := i + 1; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k]+f[k][j]+cuts[j]-cuts[i])
}
}
}
return f[0][m-1]
}Approach 4: Dynamic Programming (Another Enumeration Method)
We can also enumerate i from large to small and j from small to large. This ensures that when calculating f[i][j], the states f[i][k] and f[k][j] have already been computed, where i \lt k \lt j.
The time complexity is O(m^3), and the space complexity is O(m^2). Here, m is the length of the modified cuts array.
function minCost(n: number, cuts: number[]): number {
cuts.push(0);
cuts.push(n);
cuts.sort((a, b) => a - b);
const m = cuts.length;
const f: number[][] = Array.from({ length: m }, () => Array(m).fill(0));
for (let i = m - 2; i >= 0; --i) {
for (let j = i + 2; j < m; ++j) {
f[i][j] = 1 << 30;
for (let k = i + 1; k < j; ++k) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]);
}
}
}
return f[0][m - 1];
}func minCost(n int, cuts []int) int {
cuts = append(cuts, []int{0, n}...)
sort.Ints(cuts)
m := len(cuts)
f := make([][]int, m)
for i := range f {
f[i] = make([]int, m)
}
for i := m - 1; i >= 0; i-- {
for j := i + 2; j < m; j++ {
f[i][j] = 1 << 30
for k := i + 1; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k]+f[k][j]+cuts[j]-cuts[i])
}
}
}
return f[0][m-1]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m^3) due to nested operations over the list size. |
| Recursive with Memoization | Time Complexity: O(m^2) with memoization staving off excessive recomputation. |
| Dynamic Programming (Interval DP) | – |
| Dynamic Programming (Another Enumeration Method) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Recursive | O(2^m) | O(m) | Conceptual understanding of the problem before optimization |
| Recursive with Memoization | O(m^3) | O(m^2) | Top‑down DP when recursion is easier to reason about |
| Bottom-Up Dynamic Programming | O(m^3) | O(m^2) | Interview‑ready optimal solution with explicit DP table |
Frequently asked questions
Is Minimum Cost to Cut a Stick easy or hard?
Minimum Cost to Cut a Stick is classified as a Hard problem on LeetCode. The challenge lies in recognizing the interval dynamic programming pattern and correctly structuring subproblems based on cut boundaries.
Minimum Cost to Cut a Stick Python/Java solution
Python and Java implementations typically use either top‑down recursion with memoization or bottom‑up dynamic programming. Both approaches compute the minimum cost for every interval defined by sorted cut positions and achieve O(m^3) time complexity.
How to solve Minimum Cost to Cut a Stick in O(n)?
An O(n) solution does not exist for the general version of this problem. The structure requires evaluating different cut orders across intervals, which leads to O(m^3) time using interval dynamic programming. Attempts to greedily choose the smallest segment fail because early cuts affect future segment lengths.
What is the best approach for Minimum Cost to Cut a Stick?
Interval dynamic programming is the standard solution. After sorting the cut positions and adding boundaries 0 and n, compute the minimum cost for each segment using DP. For every interval (i, j), try all possible middle cuts and add the segment length cost. This produces an O(m^3) time and O(m^2) space solution where m is the number of cut positions.
Is Minimum Cost to Cut a Stick asked at Google/Amazon/Meta?
Interval dynamic programming problems similar to Minimum Cost to Cut a Stick appear in interviews at companies like Google, Amazon, and Meta. Variants include matrix chain multiplication and optimal BST problems, which rely on the same interval DP pattern.
What data structure is used in Minimum Cost to Cut a Stick?
The solution primarily uses arrays and a 2D dynamic programming table. The cuts array is sorted and extended with boundary values, while a DP matrix stores the minimum cost for each interval between cut positions.
What is the time complexity of Minimum Cost to Cut a Stick?
The optimal dynamic programming solution runs in O(m^3) time and O(m^2) space, where m is the number of cuts plus the two boundaries. The cubic time comes from evaluating every interval and trying every possible cut within that interval.