Minimum Cost to Cut a Stick
HardPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach models the problem using a straightforward recursive function. The core idea is that for any piece of the stick, we can try making the first cut at any of the available cut points within that piece. The total cost for a chosen first cut is the length of the current stick piece plus the minimum costs for the resulting two smaller pieces. The function then explores all possible first cuts and returns the minimum cost among them.
Algorithm
- Create a new list of cuts that includes
0andn. Sort this list. Let's call itnew_cuts. - Define a recursive function
solve(i, j)which calculates the minimum cost to cut the stick betweennew_cuts[i]andnew_cuts[j]. - In
solve(i, j):- If
j <= i + 1, it means there are no cuts to be made in this segment. Return0. - Otherwise, initialize
min_costto infinity. - Iterate
kfromi + 1toj - 1. For eachk, we consider making a cut atnew_cuts[k]. - The cost for this choice of
kis(new_cuts[j] - new_cuts[i]) + solve(i, k) + solve(k, j). - Update
min_cost = min(min_cost, current_cost). - Return
min_cost.
- If
- The initial call would be
solve(0, new_cuts.size() - 1).
Walkthrough
First, we augment the cuts array by adding the stick's boundaries, 0 and n. We then sort this new array to process the cuts in a structured manner. Let's call this new_cuts.
We define a recursive function, say solve(i, j), which computes the minimum cost to cut the stick segment defined by new_cuts[i] and new_cuts[j].
The base case for the recursion is when there are no cuts to be made between new_cuts[i] and new_cuts[j]. This happens when j is i + 1. In this case, the cost is 0.
In the recursive step, for a segment from new_cuts[i] to new_cuts[j], we iterate through all possible cut points new_cuts[k] where i < k < j. For each k, we consider it as the first cut.
The cost of making the first cut at new_cuts[k] is (new_cuts[j] - new_cuts[i]). After this cut, we have two independent subproblems: cutting the segment (new_cuts[i], new_cuts[k]) and cutting the segment (new_cuts[k], new_cuts[j]).
The total cost for choosing k is (new_cuts[j] - new_cuts[i]) + solve(i, k) + solve(k, j).
The function solve(i, j) returns the minimum of these costs over all possible k.
The final answer is obtained by calling solve(0, m-1), where m is the size of new_cuts.
import java.util.*; class Solution { public int minCost(int n, int[] cuts) { List<Integer> allCuts = new ArrayList<>(); for (int cut : cuts) { allCuts.add(cut); } allCuts.add(0); allCuts.add(n); Collections.sort(allCuts); return solve(0, allCuts.size() - 1, allCuts); } private int solve(int i, int j, List<Integer> allCuts) { if (j - i <= 1) { return 0; } int minCost = Integer.MAX_VALUE; for (int k = i + 1; k < j; k++) { int currentCost = (allCuts.get(j) - allCuts.get(i)) + solve(i, k, allCuts) + solve(k, j, allCuts); minCost = Math.min(minCost, currentCost); } return minCost; }}Complexity
Time
O(c * 2^c), where `c` is the number of cuts. The number of recursive calls grows exponentially because subproblems are recomputed.
Space
O(c) for the recursion call stack depth, where `c` is the number of cuts.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem's recursive structure.
Cons
Extremely inefficient due to massive redundant computations.
Will result in a 'Time Limit Exceeded' error for the given constraints.
This approach enhances the brute-force recursion by using memoization to avoid recomputing results for the same subproblems. We use a 2D array, memo, to store the minimum cost for cutting each possible stick segment. Before computing the cost for a segment, we check if it's already in our memo table. If so, we use the stored value; otherwise, we compute it, store it, and then return it.
Algorithm
- Create a list
allCutsfrom thecutsarray, add0andn, and sort it. Letmbe its size. - Create a 2D memoization table
memo[m][m]and initialize it with -1. - Define a recursive function
solve(i, j):- If
j - i <= 1, return 0. - If
memo[i][j]is not -1, returnmemo[i][j]. - Initialize
minCost = Integer.MAX_VALUE. - For
kfromi + 1toj - 1:currentCost = (allCuts.get(j) - allCuts.get(i)) + solve(i, k) + solve(k, j).minCost = min(minCost, currentCost).
- Store
minCostinmemo[i][j]. - Return
minCost.
- If
- Call
solve(0, m - 1).
Walkthrough
The overall structure is the same as the recursive approach. We first create a sorted list of all cut points, including 0 and n.
We introduce a 2D array, memo[m][m], where m is the number of points in our sorted list. This table will store the results of solve(i, j). We initialize it with a sentinel value (e.g., -1) to indicate that a subproblem has not been solved yet.
The recursive function solve(i, j) is modified:
- At the beginning of the function, it checks
memo[i][j]. If the value is not the sentinel, it means we have already computed the result for this subproblem, so we return the stored value immediately. - If the value is the sentinel, we proceed with the computation as in the brute-force approach.
- After computing the minimum cost, but before returning it, we store this value in
memo[i][j].
This simple addition of a lookup table drastically reduces the number of computations, changing the time complexity from exponential to polynomial.
import java.util.*; class Solution { public int minCost(int n, int[] cuts) { List<Integer> allCuts = new ArrayList<>(); for (int cut : cuts) { allCuts.add(cut); } allCuts.add(0); allCuts.add(n); Collections.sort(allCuts); int m = allCuts.size(); int[][] memo = new int[m][m]; for (int[] row : memo) { Arrays.fill(row, -1); } return solve(0, m - 1, allCuts, memo); } private int solve(int i, int j, List<Integer> allCuts, int[][] memo) { if (j - i <= 1) { return 0; } if (memo[i][j] != -1) { return memo[i][j]; } int minCost = Integer.MAX_VALUE; for (int k = i + 1; k < j; k++) { int currentCost = (allCuts.get(j) - allCuts.get(i)) + solve(i, k, allCuts, memo) + solve(k, j, allCuts, memo); minCost = Math.min(minCost, currentCost); } memo[i][j] = minCost; return minCost; }}Complexity
Time
O(c^3), where `c` is the number of cuts. Let `m = c + 2`. There are `O(m^2)` subproblems `(i, j)`. Each subproblem takes `O(m)` time to solve (the loop for `k`). Since each subproblem is solved only once, the total time is `O(m^3)`.
Space
O(c^2) for the memoization table `memo`. The recursion stack depth adds `O(c)`. So, the total space is dominated by the memoization table, `O(c^2)`.
Trade-offs
Pros
Much more efficient than brute-force.
Still relatively intuitive as it follows the recursive problem structure.
Sufficiently fast for the given constraints.
Cons
Has recursion overhead, which might make it slightly slower than a pure iterative DP solution.
This is an iterative dynamic programming approach that builds the solution from the bottom up. Instead of starting from the main problem and breaking it down, we start by solving the smallest subproblems and use their solutions to solve progressively larger ones. This eliminates recursion and its associated overhead.
Algorithm
- Create a list
allCutsfrom thecutsarray, add0andn, and sort it. Letmbe its size. - Create a 2D DP table
dp[m][m]. - Iterate
lenfrom 2 tom-1. - Iterate
ifrom 0 tom - 1 - len. - Let
j = i + len. - Initialize
minSubproblemCost = Integer.MAX_VALUE. - Iterate
kfromi + 1toj - 1. minSubproblemCost = min(minSubproblemCost, dp[i][k] + dp[k][j]).dp[i][j] = (allCuts.get(j) - allCuts.get(i)) + minSubproblemCost.- Return
dp[0][m-1].
Walkthrough
As before, we start by creating a sorted list new_cuts containing 0, n, and all the given cuts. Let m be its size.
We use a 2D DP table, dp[m][m], where dp[i][j] stores the minimum cost to cut the stick segment from new_cuts[i] to new_cuts[j].
We iterate over the length of the segments, len, from 2 up to m-1. A segment of length len (in terms of indices) corresponds to a stick piece with len-1 potential cuts inside.
For each len, we iterate through all possible starting indices i for a segment of that length. The ending index j is simply i + len.
For each (i, j) pair, we calculate dp[i][j]. The cost of the first cut on this segment is new_cuts[j] - new_cuts[i]. We need to find the best position k for this first cut (i < k < j). The total cost will be (new_cuts[j] - new_cuts[i]) + dp[i][k] + dp[k][j]. We find the minimum over all possible k.
The values dp[i][k] and dp[k][j] are already computed because they correspond to smaller segment lengths.
The final answer is stored in dp[0][m-1], which represents the minimum cost for the original stick from 0 to n.
import java.util.*; class Solution { public int minCost(int n, int[] cuts) { List<Integer> allCuts = new ArrayList<>(); for (int cut : cuts) { allCuts.add(cut); } allCuts.add(0); allCuts.add(n); Collections.sort(allCuts); int m = allCuts.size(); int[][] dp = new int[m][m]; for (int len = 2; len < m; 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++) { int cost = (allCuts.get(j) - allCuts.get(i)) + dp[i][k] + dp[k][j]; dp[i][j] = Math.min(dp[i][j], cost); } } } return dp[0][m - 1]; }}Complexity
Time
O(c^3), where `c` is the number of cuts. Let `m = c + 2`. The three nested loops for `len`, `i`, and `k` result in a cubic time complexity.
Space
O(c^2) for the 2D DP table, where `c` is the number of cuts.
Trade-offs
Pros
Most efficient approach among the three.
Avoids recursion overhead, potentially leading to better performance in practice compared to the memoized version.
Cons
Can be slightly less intuitive to formulate than the recursive top-down approach.
Solutions
Solution
class Solution {public int minCost(int n, int[] cuts) { List<Integer> nums = new ArrayList<>(); for (int x : cuts) { nums.add(x); } nums.add(0); nums.add(n); Collections.sort(nums); int m = nums.size(); int[][] f = new int[m][m]; for (int l = 2; l < m; ++l) { for (int i = 0; i + l < m; ++i) { int j = i + l; f[i][j] = 1 << 30; for (int k = i + 1; k < j; ++k) { f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + nums.get(j) - nums.get(i)); } } } return f[0][m - 1]; }}class Solution {public: int minCost(int n, vector<int> &cuts) { cuts.push_back(0); cuts.push_back(n); sort(cuts.begin(), cuts.end()); int m = cuts.size(); int f[110][110]{}; for (int l = 2; l < m; ++l) { for (int i = 0; i + l < m; ++i) { int j = i + l; f[i][j] = 1 << 30; for (int 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]; }};class Solution: def minCost(self, n: int, cuts: List[int]) -> int: cuts . extend([0, n]) cuts . sort() m = len(cuts) f = [[0] * m for _ in range(m)] for l in range(2, m): for i in range(m - l): j = i + l f[i][j] = inf for k in range(i + 1, j): f[i][j] = min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]) return f[0][- 1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.