Advanced DP

Advanced DP is not harder recursion — it's harder state design

In the 1D and 2D chapters the state was handed to you: dp[i] "best answer using the first i items," dp[i][j] "best answer for prefixes i and j." Advanced DP is the same machine — overlapping subproblems, memoize, iterate in dependency order — but you have to invent the index. The four shapes below cover almost every advanced DP asked in interviews, and each one is defined entirely by what it uses as the state: a subset (bitmask), a subtree (tree DP), a prefix of the digits of a number (digit DP), or a contiguous range (interval DP).

Bitmask DP: an integer is the visited-set

When n is small (typically n ≤ 20) and the subproblem depends on which subset of items you've used — not just how many — encode the subset as the bits of a single integer. Bit i set means "item i is used." That gives you 2ⁿ states you can index into an array directly, which is far cheaper than hashing a Set.

The bit-manipulation chapter covered these operators; the new idea here is purely that mask is a legal array index. That is what turns an exponential search over subsets into a DP over 2ⁿ cells.

Traveling Salesman — the canonical bitmask DP

"Visit every city exactly once and return to the start, minimizing total distance." Brute force is n! orderings. The DP insight: once you know which cities are visited and which one you're standing on, the cheapest completion doesn't depend on the order you visited them in. That collapses n! paths into 2ⁿ × n states.

// dist[i][j] = cost of edge i→j. Returns min cost of a tour starting and ending at 0.
// Time O(2^n · n^2), space O(2^n · n) — practical to about n = 18-20.
function tsp(dist) {
  const n = dist.length;
  if (n <= 1) return 0; // no other city to visit: the tour costs nothing
  const FULL = (1 << n) - 1;

  // dp[mask][last] = cheapest way to have visited exactly the set "mask", standing on "last"
  const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
  dp[1][0] = 0; // only city 0 visited, standing on city 0, cost 0

  for (let mask = 1; mask <= FULL; mask++) {
    if ((mask & 1) === 0) continue; // every tour includes the start city

    for (let last = 0; last < n; last++) {
      const cur = dp[mask][last];
      if (cur === Infinity) continue;        // unreachable state — skip, don't propagate Infinity
      if (((mask >> last) & 1) === 0) continue; // "last" must actually be in the visited set

      for (let next = 0; next < n; next++) {
        if ((mask >> next) & 1) continue;    // already visited
        const nextMask = mask | (1 << next);
        const cost = cur + dist[last][next];
        if (cost < dp[nextMask][next]) dp[nextMask][next] = cost;
      }
    }
  }

  let best = Infinity;
  for (let last = 1; last < n; last++) {
    best = Math.min(best, dp[FULL][last] + dist[last][0]); // close the loop back to 0
  }
  return best;
}

Dry run: tsp([[0,10,15],[10,0,20],[15,20,0]])

Closing the loop: dp[111][1] + dist[1][0] = 35 + 10 = 45, and dp[111][2] + dist[2][0] = 30 + 15 = 45 — the two candidate tours tie because a 3-city graph has only one cycle, walked in either direction. Notice mask only ever grows across the run (001 → 011/101 → 111): that's the "no dependency sort needed" property from the sticky note above, made concrete.

Two variants come up constantly. Drop the final + dist[last][0] and you get the shortest Hamiltonian path ("Shortest Path Visiting All Nodes"). Replace Math.min with a sum and you're counting orderings instead of optimizing them — same states, same loops, different combiner.

Bitmask DP without a "last" dimension — the assignment problem

Not every bitmask DP needs a second dimension. If the k-th decision is always "assign worker k," then the number of bits already set tells you which worker you're on — the popcount is a free index, so the state collapses to a single 1D array of size 2ⁿ.

// cost[w][j] = cost of giving job j to worker w. Assign every worker exactly one job.
function minAssignmentCost(cost) {
  const n = cost.length;
  const FULL = (1 << n) - 1;
  const dp = new Array(1 << n).fill(Infinity);
  dp[0] = 0;

  for (let mask = 0; mask < FULL; mask++) {
    if (dp[mask] === Infinity) continue;
    const worker = popcount(mask); // jobs assigned so far === index of the next worker

    for (let job = 0; job < n; job++) {
      if ((mask >> job) & 1) continue;
      const nextMask = mask | (1 << job);
      const cost2 = dp[mask] + cost[worker][job];
      if (cost2 < dp[nextMask]) dp[nextMask] = cost2;
    }
  }
  return dp[FULL];
}

function popcount(x) {
  let c = 0;
  while (x) { x &= x - 1; c++; } // x &= x-1 clears the lowest set bit
  return c;
}

Recognizing that a dimension is derivable from the mask is a real optimization, not cosmetics: it takes the table from O(2ⁿ·n) to O(2ⁿ) memory. Say it out loud when you spot it.

Bitmask DP when you may revisit: Shortest Path Visiting All Nodes

TSP's DP rests on one fact: every city is entered exactly once, so the mask only ever grows and the loop for mask = 0 upward is a valid order. Now change one rule. "Given a connected undirected graph with n ≤ 12 nodes, return the length of the shortest walk that visits every node. You may start anywhere, revisit nodes, and reuse edges." The state is still (node you stand on, set of nodes seen), but a step to a node you have already seen leaves the mask unchanged. From (1, 0011) you can reach (0, 0011) and then (1, 0011) again, so the states contain cycles and no loop over masks puts every dependency before its user.

Every edge costs 1, and "shortest sequence of moves between states" is exactly what BFS computes. So keep the same state, drop the table of costs, and run a BFS over the state graph. Seed it with every node at once, each with only its own bit set, because the walk may start anywhere. The first time any state with a full mask appears, the number of steps taken is the answer. A seen[node][mask] table guarantees each of the n · 2ⁿ states is expanded at most once.

function shortestPathLength(graph) {
  const n = graph.length;
  if (n === 1) return 0;
  const FULL = (1 << n) - 1;
  const seen = Array.from({ length: n }, () => new Uint8Array(1 << n)); // seen[node][mask]

  let frontier = [];
  for (let i = 0; i < n; i++) {
    frontier.push([i, 1 << i]); // start anywhere, having visited only that node
    seen[i][1 << i] = 1;
  }

  for (let steps = 0; frontier.length > 0; steps++) {
    const next = [];
    for (const [node, mask] of frontier) {
      for (const nb of graph[node]) {
        const nextMask = mask | (1 << nb);
        if (nextMask === FULL) return steps + 1; // first time any state sees every node
        if (seen[nb][nextMask]) continue;
        seen[nb][nextMask] = 1;
        next.push([nb, nextMask]);
      }
    }
    frontier = next;
  }
  return -1;
}

Dry run: the star graph [[1,2,3],[0],[0],[0]] (node 0 in the middle, leaves 1, 2, 3)

The winning walk is 1 → 0 → 2 → 0 → 3: four edges, with node 0 visited twice. A TSP-style DP that forbids revisits would find no such walk, which is the whole reason this problem is a BFS and not a loop over masks.

Complexity. There are n · 2ⁿ states and each is expanded once, looping over its node's neighbours. Summed over the nodes the neighbour counts add up to 2E, so the time is O(2ⁿ · (n + E)), and the seen table takes O(n · 2ⁿ) space. An equivalent route is to run Floyd-Warshall first to get all-pairs distances, then use the TSP path DP over those distances: with the shortest distances already baked in, revisiting a node is just a longer hop between two new nodes. It costs O(2ⁿ · n²) and is a fine second answer when the interviewer asks for a different method.

Masking the small dimension: Smallest Sufficient Team

"There are up to 16 required skills and up to 60 people, each with a set of skills. Pick the fewest people whose skills together cover every required skill." The bitmask instinct is to mask over people, but 2⁶⁰ states is impossible. Look for the dimension that is small: the skills. Let mask be the set of required skills covered so far, and let best[mask] be the smallest team found whose skills together are exactly those. Each person is a 0/1 item that turns mask into mask | personMask, so this is 0/1 knapsack where the "weight" is a set of skills and the "value" is a head count.

function smallestSufficientTeam(reqSkills, people) {
  const bitOf = new Map(reqSkills.map((skill, i) => [skill, i]));
  const FULL = (1 << reqSkills.length) - 1;

  const best = new Array(FULL + 1).fill(null); // best[mask] = smallest list of people whose skills are exactly mask
  best[0] = [];

  for (let i = 0; i < people.length; i++) {
    let personMask = 0;
    for (const skill of people[i]) if (bitOf.has(skill)) personMask |= 1 << bitOf.get(skill);
    if (personMask === 0) continue;

    for (let mask = 0; mask <= FULL; mask++) {
      if (best[mask] === null) continue;
      const nextMask = mask | personMask;
      if (nextMask === mask) continue; // this person adds nothing here (this also stops reuse of person i)
      if (best[nextMask] === null || best[mask].length + 1 < best[nextMask].length) {
        best[nextMask] = [...best[mask], i];
      }
    }
  }
  return best[FULL];
}

Two details deserve a sentence each. First, the guard nextMask === mask skips a person who adds nothing, and it also is what stops one person being used twice: if the update for person i has just written best[nextMask], reading it again with the same person gives nextMask | personMask === nextMask and does nothing. So no snapshot of the table is needed, unlike the bounded Bellman-Ford in the graph algorithms chapter. Second, people with none of the required skills are dropped at the top; they can never help.

Dry run: skills [java, nodejs, reactjs], people [java], [nodejs], [nodejs, reactjs]

The answer is best[111] = [0, 2]: two people. Time is O(P · 2^S) transitions for P people and S skills, and each improvement copies a team of at most S people, so O(P · 2^S · S) in the worst case. Storing only the team size plus a parent pointer per mask removes that copy and brings it to O(P · 2^S), at the price of one extra walk to rebuild the team.

DP on trees: the subtree is the subproblem

On a tree there are no cycles, so a post-order DFS visits every subproblem exactly once — you don't even need a memo table, the recursion tree is the DP table. The whole design question is: what summary of a subtree does the parent need? Usually it's a small tuple, and the classic shape is a pair: "best if I take this node" and "best if I don't."

// House Robber III — can't rob a node and its child. Returns max loot.
function rob(root) {
  // returns [bestIfWeRobThisNode, bestIfWeSkipThisNode]
  function dfs(node) {
    if (!node) return [0, 0];

    const [leftRob, leftSkip] = dfs(node.left);
    const [rightRob, rightSkip] = dfs(node.right);

    const robHere = node.val + leftSkip + rightSkip;  // children must be skipped
    const skipHere = Math.max(leftRob, leftSkip) + Math.max(rightRob, rightSkip); // children are free

    return [robHere, skipHere];
  }
  const [a, b] = dfs(root);
  return Math.max(a, b);
}

Note skipHere takes the max of each child independently — a common wrong version writes leftSkip + rightSkip, quietly forbidding grandchildren from being robbed. The pair-return shape makes that mistake visible because each slot has a stated meaning.

The two-value trick: what you return upward ≠ what you record

Diameter and "maximum path sum" share one subtle idea that trips people up: the best answer through a node (using both children) is not a value the parent can use, because a parent can only extend a path that goes straight down one side. So you record the two-sided value in an outer variable and return the one-sided value.

// Binary Tree Maximum Path Sum — path may start and end anywhere, values may be negative.
function maxPathSum(root) {
  let best = -Infinity;

  // returns the best DOWNWARD path sum starting at this node (usable by the parent)
  function gain(node) {
    if (!node) return 0;

    const left = Math.max(gain(node.left), 0);   // clamp at 0: a negative branch is never worth taking
    const right = Math.max(gain(node.right), 0);

    best = Math.max(best, node.val + left + right); // record the path that TURNS here — two-sided

    return node.val + Math.max(left, right);        // return the path that CONTINUES up — one-sided
  }

  gain(root);
  return best;
}

Three states per node: Binary Tree Cameras

"Install the fewest cameras on the nodes of a binary tree so that every node is watched. A camera watches its own node, its parent and its children." House Robber III needed two numbers per subtree because each node was either taken or not. Here ask the usual question: what does a parent need to know about a finished subtree? Not the whole picture, only whether the subtree's root is looked after, because that decides what the parent must do. There are exactly three cases worth distinguishing, and in all three every node strictly below the root is already covered.

Each state's cost is the fewest cameras in that subtree, and each recurrence is a choice among the children's states:

• cam: put a camera here, so each child may be in any state. The child that is need is rescued by this camera. Cost: 1 + min(all of left) + min(all of right).
• cov: no camera here, so each child must look after itself (cam or cov; need would stay uncovered), and at least one child must have a camera to cover this node. Cost: the cheaper of "left has a camera, right is cam or cov" and the mirror image.
• need: no camera here and no camera below that touches this node, so both children are cov. Cost: left.cov + right.cov.

A missing child is the base case: it can never hold a camera (cam = Infinity), it never needs rescuing (need = Infinity), and it counts as already looked after (cov = 0). That last value is what lets a node with one child work without special cases. The root has no parent to rescue it, so the answer is min(cam, cov), never need.

function minCameraCover(root) {
  const INF = Infinity;

  function dfs(node) {
    if (!node) return { cam: INF, cov: 0, need: INF }; // null: no camera possible, nothing to cover

    const L = dfs(node.left);
    const R = dfs(node.right);

    const cam = 1 + Math.min(L.cam, L.cov, L.need) + Math.min(R.cam, R.cov, R.need);
    const cov = Math.min(L.cam + Math.min(R.cam, R.cov), R.cam + Math.min(L.cam, L.cov));
    const need = L.cov + R.cov;

    return { cam, cov, need };
  }

  const { cam, cov } = dfs(root);
  return Math.min(cam, cov);
}

Dry run: root r with a single left child a, and a has two leaves b and c

The answer is min(2, 1) = 1: a single camera on a covers a, b, c and r. Time is O(n) for n nodes and space is the recursion depth. A well-known greedy (put cameras on the parents of leaves, bottom-up) is this DP with the states squeezed into one return code; the DP is what proves the greedy right, and it is the one to derive in an interview if you cannot remember the greedy's rules.

Rerooting: the answer for every node as the root

"Given a tree with n nodes, return an array where entry i is the sum of the distances from node i to every other node." Running a BFS from each node is O(n²). Rerooting does it in O(n) with a trick that applies whenever the question is "the answer if this node were the root, for every node."

Step one: solve it for one root. Root the tree at node 0. For each node u let count[u] be the number of nodes in its subtree (including u) and down[u] the sum of distances from u to the nodes inside its subtree. A child c sits one edge below its parent p, so every one of its count[c] nodes is one farther from p than from c: down[p] = sum over children c of (down[c] + count[c]). One post-order pass gives down[0], which is the answer for node 0.

Step two: move the root across one edge. Suppose you know the answer for p and want it for its child u. Moving the root from p to u brings the count[u] nodes inside u's subtree one step closer, and pushes the other n - count[u] nodes one step farther away. So

ans[u] = ans[p] - count[u] + (n - count[u])

A pre-order pass from the root applies this to every node. The two passes cost O(n) together. The code below does both without recursion, by recording an order in which every node comes after its parent and then walking that array backwards for the first pass and forwards for the second.

function sumOfDistancesInTree(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }

  const parent = new Array(n).fill(-1);
  const order = []; // every node appears after its parent
  const stack = [0];
  while (stack.length > 0) {
    const u = stack.pop();
    order.push(u);
    for (const v of adj[u]) {
      if (v !== parent[u]) {
        parent[v] = u;
        stack.push(v);
      }
    }
  }

  const count = new Array(n).fill(1); // nodes in the subtree of u
  const down = new Array(n).fill(0); // sum of distances from u to its own subtree
  for (let i = n - 1; i > 0; i--) {
    const u = order[i], p = parent[u];
    count[p] += count[u];
    down[p] += down[u] + count[u]; // every node under u is one edge farther from p
  }

  const ans = new Array(n).fill(0);
  ans[0] = down[0];
  for (let i = 1; i < n; i++) {
    const u = order[i], p = parent[u];
    ans[u] = ans[p] - count[u] + (n - count[u]); // reroot from p to u
  }
  return ans;
}

Dry run: n = 6, edges 0-1, 0-2, 2-3, 2-4, 2-5

The result in node order is [8, 12, 6, 10, 10, 10]. As a spot check, node 2 is one edge from 0, 3, 4 and 5 and two edges from 1: 1 + 1 + 1 + 1 + 2 = 6.

The general template. Rerooting is "one pass to collect what lives below, one pass to hand down what lives above." For sums of distances the only information that crosses an edge is count. For other questions (the farthest node from each node, the longest path through each node, the tree's centre) the downward pass hands down the best value excluding the child's own branch, which is why those versions keep the top two branch values per node. If a problem asks for a per-node answer over a tree, ask whether moving the root across one edge changes the answer by something you already have.

Digit DP: counting numbers up to N with a property

"How many integers in [1, N] have no two adjacent equal digits?" with N up to 10¹⁸. You cannot loop to N. Instead, build the number one digit at a time from the most significant end and count completions. Two bookkeeping flags carry all the difficulty:

• tight — every digit so far matched N's prefix exactly, so this position is capped at N's digit. Once you place something smaller, you're free (tight becomes false) and all remaining positions allow 0-9.
• started — you've placed a nonzero digit. Before that you're in leading zeros, which must not count as digits (otherwise "07" looks like it has an adjacent-pair rule applied to a zero that isn't there).

// Count integers in [1, N] with no two adjacent equal digits.
function countNoAdjacentRepeats(N) {
  const digits = String(N).split("").map(Number);
  const n = digits.length;
  const memo = new Map();

  function go(pos, prev, tight, started) {
    if (pos === n) return started ? 1n : 0n; // the all-zeros path is the number 0 — don't count it

    // Only memoize the FREE states: a tight state is visited at most once per position anyway,
    // and its count depends on N's digits, so caching it would be wrong to reuse.
    const key = pos * 100 + (prev + 1) * 2 + (started ? 1 : 0);
    if (!tight && memo.has(key)) return memo.get(key);

    const limit = tight ? digits[pos] : 9;
    let total = 0n;

    for (let d = 0; d <= limit; d++) {
      if (started && d === prev) continue; // the actual property being enforced
      total += go(
        pos + 1,
        d,
        tight && d === limit,      // stay tight only if we matched N's digit exactly
        started || d > 0
      );
    }

    if (!tight) memo.set(key, total);
    return total;
  }

  return go(0, -1, true, false);
}

Complexity is O(positions × states-per-position × 10) — here 19 × 11 × 10, about two thousand operations for N = 10¹⁸ (the 11 states are "not started" or "started with previous digit 0-9"). The counts are BigInt because the answer for N near 10¹⁸ passes 2⁵³, where ordinary numbers stop being exact; pass N as a BigInt too, as in 10n ** 18n. To count in a range [L, R], compute f(R) - f(L - 1n); that subtraction is the standard closing move and interviewers expect you to name it.

More digit DP: when the state is a running count

The adjacent-repeat problem asked "does this number have the property?" and needed prev and started in the state. Other digit problems ask for a total: how many times does the digit 1 appear when you write out every number from 1 to n? "Number of Digit One" has the answer 6 for n = 13 (1, 10, 11 twice, 12, 13). The state gains one more dimension, the number of ones placed so far, and the base case adds that count to the total instead of returning 1.

function countDigitOne(n) {
  if (n <= 0) return 0;
  const digits = String(n).split("").map(Number);
  const len = digits.length;
  const memo = new Map();

  function go(pos, ones, tight) {
    if (pos === len) return ones; // this finished number contains "ones" ones
    const key = pos * 32 + ones;
    if (!tight && memo.has(key)) return memo.get(key);

    const limit = tight ? digits[pos] : 9;
    let total = 0;
    for (let d = 0; d <= limit; d++) {
      total += go(pos + 1, ones + (d === 1 ? 1 : 0), tight && d === limit);
    }
    if (!tight) memo.set(key, total);
    return total;
  }

  return go(0, 0, true);
}

Notice what is missing: there is no started flag. Leading zeros are harmless here because a zero never adds a one, so "007" and "7" count the same. Ask of every digit DP whether the extra flag changes the answer; keep it only when it does. The memo is keyed by (pos, ones) and still skips tight states, for the reason given above.

Dry run: n = 13, digits [1, 3]

Total 1 + 5 = 6. For n = 2147483647 the same code returns 2971027783 almost instantly: there are 10 positions, at most 11 values of ones, and 10 digits per state, so roughly O(L² · 10) work for an L-digit number. That answer is still an exact JavaScript number; for bounds near 10¹⁸ switch to BigInt, as in the first digit DP.

Digit DP where the free tail collapses to a power: Digit Set

"Given a sorted list of allowed digits such as ["1","3","5","7"], count the positive integers up to n that can be written using only those digits." Here every free position has the same number of choices, k, so the memo table would hold nothing but powers of k. The DP collapses into arithmetic along the single tight path.

• Shorter numbers are all below n, and any digits may fill them: k + k² + … + kL-1 of them, for an L-digit n.
• Same length: walk n's digits from the left. At position i, each allowed digit strictly smaller than n's digit puts the number below n, and the remaining L - i - 1 positions are free: smaller · kL-i-1 numbers.
• Staying tight needs n's own digit to be allowed. If it is not, nothing longer is possible and the walk stops. If the walk gets through all L digits, n itself is buildable, so add 1.

function atMostNGivenDigitSet(digits, n) {
  const s = String(n);
  const L = s.length, k = digits.length;

  let count = 0;
  for (let len = 1; len < L; len++) count += k ** len; // every shorter number is automatically below n

  for (let i = 0; i < L; i++) {
    let smaller = 0, hasSame = false;
    for (const d of digits) {
      if (d < s[i]) smaller++;
      else if (d === s[i]) hasSame = true;
    }
    count += smaller * k ** (L - i - 1); // go below n here, the L-i-1 tail digits are free
    if (!hasSame) return count;          // cannot copy n's digit, so the tight path ends
  }
  return count + 1; // the tight path survived all L digits: n itself is buildable
}

Dry run: digits {1, 3, 5, 7}, n = 100

The answer is 20. The only 3-digit number that is not above n is 100 itself, and it contains a 0, which is not allowed. Time is O(L · k); it is the digit DP that needs no table at all.

Interval DP: solve short ranges first, and pick the last move

When the answer for [l, r] is built from answers for strictly shorter ranges inside it, iterate by increasing length, not by index. The design trick that makes these problems click is choosing the right split point semantics: for matrix chain multiplication you pick the last multiplication; for Burst Balloons you pick the last balloon to pop, because that's the only choice under which the two sides become independent.

// Burst Balloons: popping balloon i earns nums[left] * nums[i] * nums[right],
// where left/right are its CURRENT neighbours. Maximize total coins. O(n^3).
function maxCoins(nums) {
  const a = [1, ...nums, 1]; // sentinel 1s so edge balloons have neighbours
  const n = a.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));

  // dp[l][r] = best coins from bursting everything strictly between l and r,
  // with l and r themselves still standing (that's what makes the halves independent)
  for (let len = 2; len < n; len++) {          // len = distance between the exclusive bounds
    for (let l = 0; l + len < n; l++) {
      const r = l + len;
      for (let k = l + 1; k < r; k++) {        // k = the LAST balloon burst in (l, r)
        const coins = dp[l][k] + a[l] * a[k] * a[r] + dp[k][r];
        if (coins > dp[l][r]) dp[l][r] = coins;
      }
    }
  }
  return dp[0][n - 1];
}

A second interval problem, to show the shape isn't always a 2D answer table: palindrome partitioning with minimum cuts. Here the range structure only shows up in a precomputed palindrome table; the answer itself is a 1D DP over prefixes. Recognizing that split keeps this O(n²) instead of O(n³).

// Minimum cuts so every piece of s is a palindrome. O(n^2) time and space.
function minCut(s) {
  const n = s.length;
  if (n <= 1) return 0;

  const pal = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--) {          // i descending so pal[i+1][j-1] is already known
    for (let j = i; j < n; j++) {
      if (s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1])) pal[i][j] = true;
    }
  }

  const cuts = new Array(n).fill(0);
  for (let j = 0; j < n; j++) {
    if (pal[0][j]) { cuts[j] = 0; continue; } // whole prefix is already a palindrome — zero cuts
    let best = Infinity;
    for (let i = 1; i <= j; i++) {
      if (pal[i][j]) best = Math.min(best, cuts[i - 1] + 1); // cut before i
    }
    cuts[j] = best;
  }
  return cuts[n - 1];
}

Matrix chain multiplication is the same skeleton one more time: iterate by chain length, split at k, combine as dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]. If you can write Burst Balloons you can write MCM — the only difference is what the "combine" term costs.

Interval DP, again: Minimum Score Triangulation

"A convex polygon has n vertices with values v[0..n-1] in order. Cut it into n - 2 triangles by non-crossing diagonals. A triangle scores the product of its three vertex values. Minimize the total score." This is Burst Balloons in a different costume, and seeing why saves you from re-deriving it under pressure.

Look at the sub-polygon formed by vertices i..j and the chord i-j. In any triangulation of it, that chord is an edge of exactly one triangle, and the third corner of that triangle is some vertex k strictly between i and j. Fix that apex. The triangle scores v[i] · v[k] · v[j], and what remains is two smaller polygons, i..k and k..j, which share only the vertex k and cannot interfere. So choosing the triangle that sits on the closing chord (the analogue of "the last balloon") is what makes the two sides independent:

dp[i][j] = min over k in (i, j) of  dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]
dp[i][i+1] = 0   // two vertices are an edge, not a polygon

function minScoreTriangulation(values) {
  const n = values.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0)); // dp[i][j]: polygon i..j, chord i-j closes it

  for (let len = 2; len < n; len++) {
    for (let i = 0; i + len < n; i++) {
      const j = i + len;
      let best = Infinity;
      for (let k = i + 1; k < j; k++) { // k = the apex of the triangle sitting on the chord i-j
        best = Math.min(best, dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
      }
      dp[i][j] = best;
    }
  }
  return dp[0][n - 1];
}

Dry run: values [3, 7, 4, 5]

The answer is dp[0][3] = 144, the quadrilateral cut by the diagonal from vertex 0 to vertex 2. Time is O(n³) and space O(n²); the outer loop is the length of the range, as in the figure earlier in this chapter. Matrix chain multiplication has the same recurrence with a different product in the last term.

Interval DP with matching ends: Strange Printer

"A printer prints a run of the same character on one turn, and each turn may overwrite anything already printed. What is the fewest turns to print s?" For "aba" the answer is 2, not 3: print "aaa", then print "b" over the middle.

Define dp[i][j] as the fewest turns for t[i..j]. The easy upper bound is to give the last character its own turn: dp[i][j-1] + 1. The saving comes from a matching earlier character. If t[k] === t[j] for some k in [i, j-1], the turn that printed t[k] can simply be stretched to also reach position j for free. The stretched stroke covers everything between, so the middle t[k+1..j-1] gets printed afterwards, on top, independently. That costs dp[i][k] + dp[k+1][j-1]: the left part already contains the stroke that is being stretched, and the middle is a smaller interval.

function strangePrinter(s) {
  const t = [];
  for (const ch of s) if (t.length === 0 || t[t.length - 1] !== ch) t.push(ch); // "aaa" costs the same as "a"
  const n = t.length;
  if (n === 0) return 0;

  const dp = Array.from({ length: n }, () => new Array(n).fill(0)); // dp[i][j]: strokes to print t[i..j]
  for (let i = n - 1; i >= 0; i--) {
    dp[i][i] = 1;
    for (let j = i + 1; j < n; j++) {
      dp[i][j] = dp[i][j - 1] + 1; // give t[j] a stroke of its own
      for (let k = i; k < j; k++) {
        if (t[k] === t[j]) { // t[j] rides along on the stroke that printed t[k]
          const middle = k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0;
          dp[i][j] = Math.min(dp[i][j], dp[i][k] + middle);
        }
      }
    }
  }
  return dp[0][n - 1];
}

Dry run: "aba"

Collapsing consecutive duplicates first, as the code does, is not required for the recurrence to be correct but it shrinks n, and "aaabbb" becomes "ab". Time is O(n³), space O(n²). The pitfall is the empty middle: when k = j - 1 the range [k+1, j-1] is empty, and dp[j][j-1] is a cell from the unused lower triangle of the table that happens to hold 0, so the code names that case explicitly instead of relying on it. Also note the loop order: i runs downward so dp[k+1][j-1] is finished before dp[i][j] needs it, a second legal way to order interval DP.

Interval DP with a pile count: Merge Stones

"There are n piles of stones in a row. One move merges exactly K consecutive piles into one pile, at a cost equal to their total stones. Merge everything into one pile at minimum total cost, or return -1 if it is impossible." With K = 2 this is the classic interval DP. For larger K there is a new problem: a range cannot always be merged into one pile, and the leftovers matter.

When is it possible at all? Each move removes K - 1 piles (K go in, one comes out). Going from n piles to 1 takes n - 1 removals, so (n - 1) % (K - 1) must be 0. That one line is the early -1, and the same arithmetic applies to every sub-range.

The state. Let dp[i][j] be the cheapest cost to merge i..j as far as it will go. If (len - 1) % (K - 1) === 0 that is one pile; otherwise it is some number of leftover piles, and nothing more can be done inside the range. To compute it, split the range at a point where the left part becomes exactly one pile, so the left part's length must be 1 mod (K - 1). That is why m steps by K - 1 from i. The right part is merged as far as it will go. If the whole range can now be one pile, add its total stones for the final merge.

function mergeStones(stones, K) {
  const n = stones.length;
  if ((n - 1) % (K - 1) !== 0) return -1; // every merge removes K-1 piles; this decides if one pile is reachable

  const prefix = [0];
  for (const x of stones) prefix.push(prefix[prefix.length - 1] + x);

  const dp = Array.from({ length: n }, () => new Array(n).fill(0)); // dp[i][j]: cheapest way to shrink i..j as far as possible
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      const j = i + len - 1;
      let best = Infinity;
      for (let m = i; m < j; m += K - 1) { // [i..m] becomes ONE pile, so m steps by K-1
        best = Math.min(best, dp[i][m] + dp[m + 1][j]);
      }
      if ((len - 1) % (K - 1) === 0) best += prefix[j + 1] - prefix[i]; // the final merge into one pile
      dp[i][j] = best;
    }
  }
  return dp[0][n - 1];
}

Dry run: stones [3, 5, 1, 2, 6], K = 3

The answer is 25: merge 5, 1, 2 for 8, then 3, 8, 6 for 17. Time is O(n³ / K) because the split loop skips K - 1 positions at a time, and space is O(n²). The alternative formulation dp[i][j][piles] also works, but it adds a third dimension for the pile count, with the extra memory and time that brings; the "merge as far as it goes" definition is what removes that dimension.

DP over a DAG: memoized DFS on an implicit graph

Some DP problems have no array to loop over, because the states are the cells of a grid and the moves between them depend on the data. "Given a matrix of integers, find the length of the longest path that moves up, down, left or right to a strictly larger value." The cells are the states, a move is an edge, and because every move strictly increases the value, the edges can never form a cycle: the states are a DAG.

On a DAG, "the longest path starting at this cell" depends only on the cells it can move to, so the recurrence is longest(cell) = 1 + max(longest(next)) over strictly larger neighbours. There is no obvious loop order, but you do not need one: write the recursion, cache each answer, and the recursion visits the cells in an order that works. A memoized DFS is a post-order walk of the DAG, so a cell's answer is always ready before anything that needs it.

function longestIncreasingPath(matrix) {
  const R = matrix.length, C = matrix[0].length;
  const memo = Array.from({ length: R }, () => new Array(C).fill(0)); // 0 = not computed yet
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function go(r, c) {
    if (memo[r][c] !== 0) return memo[r][c];
    let best = 1; // the cell alone
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
      if (matrix[nr][nc] <= matrix[r][c]) continue; // strictly larger only: this is what keeps the graph acyclic
      best = Math.max(best, 1 + go(nr, nc));
    }
    memo[r][c] = best;
    return best;
  }

  let answer = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) answer = Math.max(answer, go(r, c));
  }
  return answer;
}

Dry run: [[9, 9, 4], [6, 6, 8], [2, 1, 1]]

The answer is 4, the path 1 → 2 → 6 → 9. (The table lists cells in the order they finish, which is not the scan order: the scan reaches (0,2) third, and that call cannot finish until it has computed (1,2) below it.) Every cell is computed once and looks at four neighbours, so the time is O(R · C) with O(R · C) memory for the cache.

The same idea in other clothes: "number of paths from the top-left to the bottom-right with obstacles", "count the increasing paths in a grid" and "the longest path in a DAG" are all memoized recursion over a graph whose edges point only forward. The graph algorithms chapter shows the iterative form, relaxing edges in topological order.

Monotone-deque DP: the best of the last k states

"Given an integer array and k, find the maximum sum of a non-empty subsequence in which any two consecutive chosen elements are at most k positions apart." Let dp[i] be the best sum of a valid subsequence that ends at index i. It either starts at i, giving nums[i], or extends a subsequence ending at some j in [i - k, i - 1]:

dp[i] = nums[i] + max(0, max of dp[j] for j in [i-k, i-1])

Evaluated directly, that inner maximum is a scan of k values for each i, so O(n · k). But the inner maximum is a sliding-window maximum over the dp array you are building, and the monotonic deque from the monotonic stack and queue chapter answers it in amortized O(1). The deque holds indices whose dp values decrease from front to back. Before reading the front, drop indices that fell out of the window. After computing dp[i], drop every index at the back whose value is not larger, because it is older than i and no better, so it can never be the window maximum again.

function constrainedSubsetSum(nums, k) {
  const n = nums.length;
  const dp = new Array(n).fill(0); // dp[i]: best sum of a valid subsequence that ENDS at i
  const queue = new Array(n);      // indices whose dp values decrease from head to tail
  let head = 0, tail = 0;
  let best = -Infinity;

  for (let i = 0; i < n; i++) {
    while (head < tail && queue[head] < i - k) head++; // fell out of the window of the last k indices
    const bestPrevious = head < tail ? dp[queue[head]] : 0;
    dp[i] = nums[i] + Math.max(0, bestPrevious);       // extend the best earlier chain, or start fresh
    best = Math.max(best, dp[i]);

    while (head < tail && dp[queue[tail - 1]] <= dp[i]) tail--; // dominated: older AND not better
    queue[tail++] = i;
  }
  return best;
}

Dry run: nums [10, 2, -10, 5, 20], k = 2

The answer is the largest dp value, 37, from the subsequence 10, 2, 5, 20. Each index enters and leaves the deque once, so the time is O(n) with O(n) space for dp and the deque's backing array.

State compression: making a big state fit

Once the state has three or four dimensions, memory becomes the binding constraint before time does. Three techniques cover most of it:

Games and probability: where this chapter stops

Two families of DP problems look like they belong here but are a separate topic that this chapter does not teach. In a two-player game such as "Can I Win" or the stone games, the state is the position and the value is "does the player to move win" or "by how much do they lead", defined from the mover's side so that a turn flip is one negation. The bitmask and interval tools above are the state, and the new idea is the minimax step. In a probability or expected-value DP such as "Knight Probability in a Chessboard" or "Soup Servings", the transitions are weighted by chances and the answer is a sum instead of a min. If a problem mentions turns, optimal play, or "the probability that", it is one of these; the state design from this chapter carries over unchanged.

Recognizing it in an unseen problem

• n ≤ 20 with permutations, assignments, or "visit all" → bitmask DP. The tiny constraint is the giveaway; interviewers set n = 12-18 precisely to signal 2ⁿ.
• "Maximum/minimum over a tree, with a constraint between parent and child" → tree DP with a tuple return. Ask what a parent needs from a subtree; that tuple is your state.
• N up to 10⁹-10¹⁸ and the question is "how many numbers ≤ N satisfy…" → digit DP. Nothing else fits a bound that large, and the answer is a count, not a search.
• "Merge adjacent," "burst," "remove and the neighbours join," "partition a string into pieces" → interval DP. Loop by length; the split point is usually the last operation, not the first.
• Distinguish from plain 2D DP: 2D DP indexes two independent sequences; interval DP indexes two ends of the same sequence and must be filled so shorter ranges are ready first, usually by length.
• Distinguish from greedy: if a locally best choice can be invalidated by a later one (bursting the biggest balloon first is not optimal), greedy is out — the fact that "obvious greedy" fails on a small counterexample is the strongest signal you're in advanced-DP territory.
• A walk that may revisit nodes, shortest, over a small graph → the state is still (subset, current), but the states contain cycles. Run a BFS over them instead of a loop over masks.
• "For every node as the root" → rerooting: one pass up to collect what lies below, one pass down moving the root across each edge.
• "dp[i] = cost + the best of the previous k states" → a monotonic deque over the dp values, which makes it linear.
• A grid or graph where each move strictly increases something → memoized DFS over a DAG; the strictness is what makes the memo safe.
• Common pitfall across all of these: propagating Infinity from unreachable states into arithmetic. Always continue on unreachable before relaxing.