Watch 10 video solutions for Minimum Cost to Cut a Stick, a hard level problem involving Array, Dynamic Programming, Sorting. This walkthrough by NeetCodeIO has 20,686 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 - 1cuts array are distinct.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 | 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 |