Blind Plus 100 Visualized

#96 · 2D DP

Minimum Cost to Cut a Stick

A wooden stick of length n has marks at the positions in cuts. Cutting a stick costs the length of the stick being cut. Choose the order of cuts to minimise the total cost, and return that minimum.

HardLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sorted cut points with both ends

Sort the cuts and add the ends 0 and n. A piece of the stick is then just a pair of indices (i, j) of these points, and cutting at k splits it into (i, k) and (k, j).

Memory layout

One sorted array of m = cuts + 2 numbers.

OperationCost
sortO(m log m)

Interval DP table

dp[i][j] = cheapest total to make every cut strictly inside piece (i, j). The first cut at k costs the piece length and leaves two independent pieces: dp[i][j] = min over k of dp[i][k] + dp[k][j] + (pts[j] − pts[i]).

Memory layout

An m × m array; only the upper triangle is used.

OperationCost
plain DPO(m³)
with Knuth optimisationO(m²)

Optimal-split table (Knuth)

opt[i][j] stores the best first cut for each piece. For this cost structure the optimal cut is monotone: opt[i][j − 1] ≤ opt[i][j] ≤ opt[i + 1][j], so each window of candidate cuts is small and they overlap telescopically along a diagonal.

Memory layout

A second m × m integer array.

OperationCost
amortised work per diagonalO(m)

Why it fits

  • After the first cut the two pieces are independent, so subproblems are just sub-intervals of the sorted points: classic interval DP.
  • The cost of a cut depends only on the length of the current piece, a fixed function of (i, j), which is what makes the quadrangle inequality, and therefore Knuth's optimisation, apply.
  • Sorting turns "which cuts are inside this piece" into a contiguous index range.

Why alternatives degrade

Trying all orderings of cuts:
k! orders; k = 100 is hopeless.
Greedy (always cut the middle / the largest piece):
Costs depend on the whole future order; there are easy counterexamples.
Divide and conquer without caching:
The same pieces recur under different orders of earlier cuts.

Four approaches, from naive to production

1 · beginner

Plain recursion on the first cut

time O(3^m)space O(m)

Sort the cuts and add the ends. For a piece (i, j) try each inner point k as the FIRST cut: it costs the piece length and splits the piece in two independent sub-problems. Take the cheapest.

int minCost(int n, vector<int>& cuts) {
    vector<int> pts{0}; pts.insert(pts.end(), cuts.begin(), cuts.end()); sort(pts.begin() + 1, pts.end()); pts.push_back(n);
    function<int(int, int)> solve = [&](int i, int j) -> int {
        if (j - i < 2) return 0;
        int best = INT_MAX;
        for (int k = i + 1; k < j; k++) {
            best = min(best, solve(i, k) + solve(k, j) + pts[j] - pts[i]);
        }
        return best;
    };
    return solve(0, (int)pts.size() - 1);
}

Flaws & bottlenecks

  • The same sub-pieces are solved again and again.
  • Roughly three-way branching: exponential time.
  • Recursion depth up to m.

Interviewer cross-questions

Why does the order of cuts inside different pieces not matter?

Say: After a cut the two pieces never interact: their costs are the sums of their own cuts, so each can be optimised independently.

What is the base case?

Say: Two neighbouring points enclose no cut position, so the cost is 0.

How do you speed it up?

Say: Cache solve(i, j) by its two indices.

2 · intermediate

Memoised recursion

time O(m³)space O(m²)

Same recursion with a memo table indexed by (i, j): each of the O(m²) pieces is solved once, trying O(m) first cuts.

int minCost(int n, vector<int>& cuts) {
    vector<int> pts{0}; pts.insert(pts.end(), cuts.begin(), cuts.end()); sort(pts.begin() + 1, pts.end()); pts.push_back(n);
    vector<vector<int>> memo(pts.size(), vector<int>(pts.size(), -1));
    function<int(int, int)> solve = [&](int i, int j) -> int {
        if (j - i < 2) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int best = INT_MAX;
        for (int k = i + 1; k < j; k++) {
            best = min(best, solve(i, k) + solve(k, j) + pts[j] - pts[i]);
        }
        memo[i][j] = best;
        return best;
    };
    return solve(0, (int)pts.size() - 1);
}

Flaws & bottlenecks

  • Recursion depth up to m.
  • Call overhead per state.
  • Still cubic.

Interviewer cross-questions

Why O(m³)?

Say: m² pieces times up to m choices of first cut each.

What if cuts are given unsorted?

Say: Sort first; the DP relies on pieces being contiguous index ranges.

How do you avoid recursion?

Say: Iterate over piece lengths, short to long.

3 · advanced

Bottom-up by piece length

time O(m³)space O(m²)

For gap = 2 … m − 1 and each start i, set dp[i][j] = min over k of dp[i][k] + dp[k][j], plus the piece length pts[j] − pts[i].

int minCost(int n, vector<int>& cuts) {
    vector<int> pts{0}; pts.insert(pts.end(), cuts.begin(), cuts.end()); sort(pts.begin() + 1, pts.end()); pts.push_back(n);
    int m = pts.size();
    vector<vector<int>> dp(m, vector<int>(m, 0));
    for (int gap = 2; gap < m; gap++) {
        for (int i = 0; i + gap < m; i++) {
            int j = i + gap;
            int best = INT_MAX;
            for (int k = i + 1; k < j; k++) best = min(best, dp[i][k] + dp[k][j]);
            dp[i][j] = best + pts[j] - pts[i];
        }
    }
    return dp[0][m - 1];
}

Flaws & bottlenecks

  • Cubic time: 100 cuts is fine, but 10⁴ would not be.
  • Quadratic memory.
  • Does not exploit the monotone structure of the best cut.

Interviewer cross-questions

Why add the piece length once, outside the min?

Say: It is the same for every choice of k (the cost of the first cut depends only on the piece), so it can be added after taking the minimum.

How do you recover the cutting order?

Say: Store the argmin k per piece and expand recursively: cut at k, then cut each side.

Which structural property permits something faster?

Say: The best cut is monotone in the piece boundaries (quadrangle inequality), which is what Knuth's optimisation uses.

4 · expert

Knuth's optimisation: O(m²)

time O(m²)space O(m²)

Record opt[i][j], the best first cut. When solving (i, j), only try cuts k between opt[i][j − 1] and opt[i + 1][j] (clamped to i + 1 … j − 1). The windows telescope along each diagonal, giving O(m²) in total.

int minCost(int n, vector<int>& cuts) {
    vector<int> pts{0}; pts.insert(pts.end(), cuts.begin(), cuts.end()); sort(pts.begin() + 1, pts.end()); pts.push_back(n);
    int m = pts.size();
    vector<vector<int>> dp(m, vector<int>(m, 0));
    vector<vector<int>> opt(m, vector<int>(m, 0));
    for (int i = 0; i + 1 < m; i++) opt[i][i + 1] = i + 1;
    for (int gap = 2; gap < m; gap++) {
        for (int i = 0; i + gap < m; i++) {
            int j = i + gap;
            int lo = max(opt[i][j - 1], i + 1);
            int hi = min(opt[i + 1][j], j - 1);
            dp[i][j] = INT_MAX;
            for (int k = lo; k <= hi; k++) {
                int cost = dp[i][k] + dp[k][j] + pts[j] - pts[i];
                if (cost < dp[i][j]) { dp[i][j] = cost; opt[i][j] = k; }
            }
        }
    }
    return dp[0][m - 1];
}

Flaws & bottlenecks

  • Correct only when the cost satisfies the quadrangle inequality; blindly applying it elsewhere gives wrong answers.
  • Another m × m table of memory.
  • Subtle boundary clamps and seeding of opt for neighbouring points.

Interviewer cross-questions

Why can the search window be narrowed?

Say: For this cost (fixed by the piece length) the optimal first cut never moves left when the piece is extended to the right, and never moves right when it is extended to the left, so opt[i][j−1] ≤ opt[i][j] ≤ opt[i+1][j].

Why is the total work O(m²)?

Say: Along a diagonal the window of (i, j) ends where the window of (i + 1, j + 1) starts; the sum of window sizes telescopes to O(m).

How do you check the optimisation is valid before using it?

Say: Test the quadrangle inequality for the cost function, or verify against the cubic DP on random inputs, as this solution's tests do.

Synchronized code walkthrough

Showing: Plain recursion on the first cut — shares the player above; click any step to jump.

int minCost(int n, vector<int>& cuts) {
    vector<int> pts{0}; pts.insert(pts.end(), cuts.begin(), cuts.end()); sort(pts.begin() + 1, pts.end()); pts.push_back(n);
    function<int(int, int)> solve = [&](int i, int j) -> int {
        if (j - i < 2) return 0;
        int best = INT_MAX;
        for (int k = i + 1; k < j; k++) {
            best = min(best, solve(i, k) + solve(k, j) + pts[j] - pts[i]);
        }
        return best;
    };
    return solve(0, (int)pts.size() - 1);
}