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;
  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;
}

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.

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;
}

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 ? 1 : 0; // 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 = 0;

    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 × 20 × 10, a few thousand operations for N = 10¹⁸. To count in a range [L, R], compute f(R) - f(L - 1); that subtraction is the standard closing move and interviewers expect you to name it.

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.

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:

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 by length, not row by row.
• 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.
• Common pitfall across all four: propagating Infinity from unreachable states into arithmetic. Always continue on unreachable before relaxing.