Interval DP · Podium

Matrix-chain multiplication, bursting balloons, optimal BST, CSES Removal Game / Rectangle Cutting: the subproblem is a contiguous interval. You try every split (or every last balloon), take min or max.

n ≤ 400 is the O(n³) gate (400³ = 6.4e7). n ≤ 800 needs Knuth optimization or a better split. n = 2000 is not interval DP unless the inner loop is O(1).

Loop by length. If you loop l then r without ensuring r-l grows, you read uninitialized splits.

Matrix chain: dims[i]×dims[i+1], return min multipliesjs

function matrixChain(dims) {
  const n = dims.length - 1; // n matrices
  const dp = Array.from({ length: n }, () => Array(n).fill(0));
  for (let len = 2; len <= n; len++) {
    for (let l = 0; l + len - 1 < n; l++) {
      const r = l + len - 1;
      let best = Infinity;
      for (let k = l; k < r; k++) {
        const cost = dp[l][k] + dp[k + 1][r] + dims[l] * dims[k + 1] * dims[r + 1];
        if (cost < best) best = cost;
      }
      dp[l][r] = best;
    }
  }
  return n === 0 ? 0 : dp[0][n - 1];
}

TRACE

dims [10, 20, 30, 40] — three matrices 10×20, 20×30, 30×40.

len 1

Single matrix: 0 multiplies. dp[i][i]=0.

1 / 4

CHECK

Burst balloons: bursting i in (l, r) last scores l*i*r plus dp on the two sides. Why last, not first?

CHECK

n=400, O(n³) interval DP in JS. Is it legal in this arena?

Checks 0/2

Next lesson