Log inSign up
hardLeetCodeNot Started

Minimum Cost to Cut a Stick

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

Given a wooden stick of length n units. The stick is labelled from 0 to n. You are also given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in any 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 k 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).

Return the minimum total cost of the cuts.

### Example 1 - Input: n = 7, cuts = [1, 3, 4, 5] - Output: 16 - Explanation: Using cut order [3, 5, 1, 4]: 1. Cut at 3: stick length is 7 -> cost 7. Remaining sticks: [0, 3] and [3, 7]. 2. Cut at 5: stick length is 4 (from 3 to 7) -> cost 4. Remaining: [0, 3], [3, 5], [5, 7]. 3. Cut at 1: stick length is 3 (from 0 to 3) -> cost 3. Remaining: [0, 1], [1, 3], [3, 5], [5, 7]. 4. Cut at 4: stick length is 2 (from 3 to 5) -> cost 2. - Total cost = 7 + 4 + 3 + 2 = 16.

### Example 2 - Input: n = 9, cuts = [5, 6, 1, 4, 2] - Output: 22

Constraints:

  • 2 <= n <= 106
  • 1 <= cuts.length <= 100
  • 1 <= cuts[i] <= n - 1
  • All elements in cuts are distinct

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize and formulate interval dynamic programming problems.
  • Transform an arbitrary cut ordering problem into partition DP.
  • Implement both memoized recursion and iterative length-based DP.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Order of operations matters.
  • Cost depends on the current span length.
  • Subproblems become smaller sub-segments of the original range.

Algorithmic Decision Tree:

  • Boundary endpoints 0 and n must be added to cuts.
  • Sort cuts array so intervals are monotonically increasing.

Connected Patterns:

Matrix Chain MultiplicationBurst BalloonsOptimal Binary Search Tree

1. Recursive Permutation of Cuts

Intuition

Recursively try every possible cut as the first cut, dividing the stick into two sub-sticks.

Algorithm

  1. Define solve(left, right, availableCuts).
  2. For each cut in availableCuts within (left, right):
  3. Cost = (right - left) + solve(left, cut) + solve(cut, right).
  4. Return minimum cost among all choices.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8class Solution {
9 int solve(int left, int right, const vector<int>& cuts) {
10 int minCost = 1e9;
11 bool hasCut = false;
12 for (int c : cuts) {
13 if (c > left && c < right) {
14 hasCut = true;
15 int cost = (right - left) + solve(left, c, cuts) + solve(c, right, cuts);
16 minCost = min(minCost, cost);
17 }
18 }
19 return hasCut ? minCost : 0;
20 }
21public:
22 int minCost(int n, vector<int>& cuts) {
23 return solve(0, n, cuts);
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> cuts = {1, 3, 4, 5};
30 cout << "Min Cost: " << sol.minCost(7, cuts) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(c!)
  • Space complexity: O(c) call stack

2. Memoized Top-Down Interval DP

Intuition

Sort cuts with boundaries 0 and n. Use a 2D memo table indexed by cut indices (i, j).

Algorithm

  1. Add 0 and n to cuts, then sort.
  2. Let m = cuts.size().
  3. Define solve(i, j): min cost to make cuts strictly between index i and index j.
  4. Base case: if i + 1 == j, return 0 (no cuts left between them).
  5. Try every cut index k from i + 1 to j - 1:
  6. cost = (cuts[j] - cuts[i]) + solve(i, k) + solve(k, j).
  7. Memoize memo[i][j] and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int i, int j, const vector<int>& cuts, vector<vector<int>>& memo) {
9 if (i + 1 >= j) return 0;
10 if (memo[i][j] != -1) return memo[i][j];
11
12 int minCost = 1e9;
13 for (int k = i + 1; k < j; ++k) {
14 int cost = (cuts[j] - cuts[i]) + solve(i, k, cuts, memo) + solve(k, j, cuts, memo);
15 minCost = min(minCost, cost);
16 }
17 return memo[i][j] = minCost;
18 }
19public:
20 int minCost(int n, vector<int>& cuts) {
21 cuts.push_back(0);
22 cuts.push_back(n);
23 sort(cuts.begin(), cuts.end());
24 int m = cuts.size();
25 vector<vector<int>> memo(m, vector<int>(m, -1));
26 return solve(0, m - 1, cuts, memo);
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> cuts = {1, 3, 4, 5};
33 cout << "Min Cost: " << sol.minCost(7, cuts) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(c^3)
  • Space complexity: O(c^2)

3. Iterative Interval DP (Bottom-Up)

Intuition

Tabulate interval lengths from 2 to m - 1 to solve subproblems in increasing interval size.

Algorithm

  1. Augment cuts with 0 and n, then sort; let length be m.
  2. Initialize dp[m][m] with 0.
  3. Loop interval length len from 2 to m - 1:
  4. Loop starting index i from 0 to m - len - 1:
  5. Let j = i + len.
  6. dp[i][j] = infinity.
  7. For k from i + 1 to j - 1:
  8. dp[i][j] = min(dp[i][j], (cuts[j] - cuts[i]) + dp[i][k] + dp[k][j]).
  9. Return dp[0][m - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minCost(int n, vector<int>& cuts) {
10 cuts.push_back(0);
11 cuts.push_back(n);
12 sort(cuts.begin(), cuts.end());
13 int m = cuts.size();
14
15 vector<vector<int>> dp(m, vector<int>(m, 0));
16
17 for (int len = 2; len < m; ++len) {
18 for (int i = 0; i + len < m; ++i) {
19 int j = i + len;
20 int minCost = 1e9;
21 for (int k = i + 1; k < j; ++k) {
22 minCost = min(minCost, (cuts[j] - cuts[i]) + dp[i][k] + dp[k][j]);
23 }
24 dp[i][j] = minCost;
25 }
26 }
27
28 return dp[0][m - 1];
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<int> cuts = {1, 3, 4, 5};
35 cout << "Min Cost: " << sol.minCost(7, cuts) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(c^3)
  • Space complexity: O(c^2)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive PermutationO(c!)O(c)Exhaustive evaluation of all cut orderings.c! permutations
2.Memoized Top-Down DPO(c^3)O(c^2)Sort cuts and memoize subproblem ranges (i, j).O(c3) transitions
3.Iterative Interval DPOptimalO(c^3)O(c^2)Bottom-up tabulation over interval lengths from 2 to m.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Indexing DP table by stick length n (up to 106) instead of cuts array index (up to 100): would lead to O(n3) and Out of Memory.

Pitfall 2:

Forgetting to add 0 and n as stick boundaries.

Crucial Edge Cases to Validate:

  • Single cut: cuts = [c]. Answer is always n.
  • Cuts already sorted: Sorting step is an idempotent O(c log c) operation.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain to the interviewer why we index by cuts array size c rather than stick length n: c <= 100 allows O(c3) ~ 106 ops, whereas n <= 106 would make O(n3) impossible.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we add 0 and n to the cuts array and sort it before applying DP?

Back to DSA Sheet