Minimum Cost to Cut a Stick

Problem

Given a stick of length n (positions 0..n) and an array cuts of positions where cuts must happen, make all cuts. Each cut costs the current length of the piece being cut. Return the minimum total cost over all cutting orders.

Intuition

Cut order matters: cutting the stick into a short piece first leaves a long piece to keep paying for. You can't naively greedy — example: [1, 3, 4, 5] with greedy-smallest-first gives 7 + 6 + 4 + 3 = 20, worse than optimal 16. Greedy-largest-first sometimes works, sometimes doesn't. The problem wants the provable minimum.

The right shape is #312's reframe: ask which cut happens last in each segment. When cut k is the last one in segment (L, R), at that moment the piece's length is exactly R - L (no cuts remain inside), and the two sides (L, k) and (k, R) are fully independent.

Sort cuts and pad with [0, n] so cuts[0] = 0 and cuts[m - 1] = n. Let dp[i][j] = minimum cost to make all cuts strictly between indices i and j (in the padded array). Then:

dp[i][j] = min_{k in (i, j)} dp[i][k] + dp[k][j] + (cuts[j] - cuts[i])

Base: dp[i][j] = 0 when j - i < 2 (no cuts inside this interval). Answer: dp[0][m - 1].

The (cuts[j] - cuts[i]) term is exactly the length of the piece at the moment the last cut is made — identical to Burst Balloons' v[l] * v[k] * v[r] except we sum instead of multiply.

Approach

impl Solution {
    pub fn min_cost(n: i32, mut cuts: Vec<i32>) -> i32 {
        cuts.push(0);
        cuts.push(n);
        cuts.sort();
        let m = cuts.len();
        let mut dp = vec![vec![0i32; m]; m];
        for len in 2..m {
            for i in 0..(m - len) {
                let j = i + len;
                let mut best = i32::MAX;
                for k in (i + 1)..j {
                    let cost = dp[i][k] + dp[k][j] + (cuts[j] - cuts[i]);
                    if cost < best {
                        best= cost;
                    }
                }
                dp[i][j]= best;
            }
        }
        dp[0][m - 1]
    }
}

function minCost(n: number, cuts: number[]): number {
  const padded = [0, n, ...cuts].sort((a, b) => a - b);
  const m = padded.length;
  const dp: number[][] = Array.from({ length: m }, () => new Array(m).fill(0));
  for (let len = 2; len < m; len++) {
    for (let i = 0; i + len < m; i++) {
      const j = i + len;
      let best = Infinity;
      for (let k = i + 1; k < j; k++) {
        const cost = dp[i][k] + dp[k][j] + (padded[j] - padded[i]);
        if (cost < best) best = cost;
      }
      dp[i][j] = best;
    }
  }
  return dp[0][m - 1];
}

Trace

Padded sorted cuts for n = 7, cuts = [1, 3, 4, 5]: [0, 1, 3, 4, 5, 7] (indices 0–5).

Return dp[0][5] = 16. ✓

Edge cases

• Empty cuts — return 0. Padded array is [0, n], length 2, no interior. The loop body never runs.
• Single cut — only one position to consider at length 2. The best k is trivially that cut; cost is n.
• Cuts that are already sorted — harmless; the sort is idempotent.
• cuts contains 0 or n — LC constraints disallow this. If it could happen, sort_dedup first so the padding doesn't introduce a duplicate that breaks the dp[i][j] = 0 base case.

Takeaway

Cut Stick is the "last X" interval-DP template applied to a scalar cost instead of Burst Balloons' multiplicative cost. Learn the pair: dp[i][j] = min/max over k of dp[i][k] + dp[k][j] + f(i, k, j), where f depends on the problem. The space of variations is large, but the template doesn't change.

If you internalize this, Stage-4's chain-reaction problems (intervals with overlapping constraints, weighted choices, compound actions) are just variations on these three recurrences you've now written: match-or-skip (LCS/Edit Distance), take-or-skip (knapsack), and last-X (interval DP).