Minimum Cost to Cut a Stick - Solution & Explanation
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.
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.
This C solution sorts the cuts and inserts them along with the stick boundaries into a new array 'newCuts'. The dynamic programming table 'dp' is used to record minimum costs for every subproblem defined by start and end positions in the newCuts array. The cost of each subproblem is solved by iterating over possible cut positions within that range and selecting the smallest achievable cost.
Complexity
Time Complexity: O(m^3) where m is the number of cuts, due to the nested loops solving subproblems.
Space Complexity: O(m^2) for the dp table storage, where m is the number of cuts.
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.
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.
Complexity
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.
Code
Python
Java
C++
Go
TypeScript
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m^3) where m is the number of cuts, due to the nested loops solving subproblems. |
| Recursive with Memoization | Time Complexity: O(m^2) with memoization staving off excessive recomputation. |
| Dynamic Programming (Interval DP) | — |
| Dynamic Programming (Another Enumeration Method) | — |
Detailed 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 |
Video Solution
DP 50. Minimum Cost to Cut the Stick • take U forward • 250,375 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Cost to Cut a Stick easy or hard?
Minimum Cost to Cut a Stick Python/Java solution
How to solve Minimum Cost to Cut a Stick in O(n)?
What is the best approach for Minimum Cost to Cut a Stick?
Is Minimum Cost to Cut a Stick asked at Google/Amazon/Meta?
What data structure is used in Minimum Cost to Cut a Stick?
What is the time complexity of Minimum Cost to Cut a Stick?
Ready to solve this problem?
Practice Minimum Cost to Cut a Stick with our built-in code editor and test cases.
Practice on FleetCode