Dynamic programming: advanced shapes

advancedCommon atGoogleMetatrading firmsRead firstDynamic programming: 1DDynamic programming: 2DBit manipulationPractise in the Sandbox →

Beyond prefixes, four state shapes cover most hard DP questions. Interval DP: dp[i][j] over a range, filled by length, O(n³) when you try every split. Bitmask DP: the state includes a set encoded as an integer’s bits, O(2ⁿ · n) states, fine for n ≤ ~20. Knapsack: (item, remaining budget), pseudo-polynomial O(n · W). Tree DP: a few numbers per node computed children-first, O(n). The hard part is always the state; the fill order follows from it.

The idea in plain words

1-D and 2-D DP ask “what about a prefix?”. Many problems don’t decompose that way:

• Intervals. “Best way to combine / split the range i..j.” The last operation splits the range in two, and both halves are smaller ranges. Think of choosing where to put the outermost brackets.
• Subsets. “Which items have I already used?” When order matters and n is small, the set of used items is the state. A set of up to ~20 items fits in an integer: bit k = item k used.
• Budgets. “Items so far, with this much capacity left.” The second index is a number (weight, money, time), not a position. See the dedicated knapsack page.
• Trees. “Best answer for this subtree, given one fact about its root” (picked or not, coloured red or blue). Children are independent once you fix that fact, so you combine them bottom-up.

Each shape has a natural order: by interval length, by mask value (adding a bit makes the number bigger), by item index, or post-order on the tree.

See it

Three shapes, three small visualizations. Arrows point from the states a cell reads to the cell being filled.

Interval DP: where to split

Matrix-chain multiplication: the cost of multiplying M_i..M_j is the cost of the two halves plus the cost of the final multiplication. The table fills diagonal by diagonal (by length). Change the dimensions and see the best bracketing change.

Interval DP: matrix-chain order

step through

dimensions d0, d1, …, dn (Mk is dk × dk+1)

matrices5

interval being solvedthe two halves of the best splitunused (i > j)

State dp[i][j] = cheapest way to multiply matrices Mi..Mj. A single matrix costs nothing, so the diagonal is 0.

↺◀▶ Play▶1 / 12

Bitmask DP: the visited set as bits

Shortest tour through 4 cities (the Held-Karp algorithm). A row is a set of visited cities written in binary; a column is the city you’re standing on. Every transition adds one bit, so processing masks in increasing numeric order always has the predecessors ready.

Bitmask DP: shortest tour of 4 cities (Held-Karp)

step through

0

0

0

1

mask bits: city 3 2 1 0

mask0001

last0

state being filledbest predecessor statelast cityvisited

Bit k of the mask = "city k visited". Base: mask 0001 (only home), standing at city 0, distance 0.

↺◀▶ Play▶1 / 14

Tree DP: two answers per node

Minimum vertex cover: pick the fewest nodes so every edge has a picked endpoint. Each node returns its subtree’s best answer twice, once assuming it’s picked and once assuming it isn’t.

Tree DP: two answers per node, children first

step through

node being combinedsubtree solvedin the cover

Each node returns two answers for its subtree: "in" (this node is picked) and "out" (it isn't). Leaves are solved first: post-order.

↺◀▶ Play▶1 / 11

When to reach for it

The problem says…	Shape	Why
“merge / burst / cut / bracket a sequence; cost depends on neighbours”	Interval	The last operation splits [i..j] into two independent smaller ranges.
“palindromic…”, “optimal play from either end of a row”	Interval	State = both ends of the remaining range.
n ≤ 20 and “visit all / assign each / choose a subset where order matters”	Bitmask	2²⁰ ≈ 10⁶ sets is affordable; n! orderings isn’t.
“subset with total ≤ W / exactly W”, “unlimited copies”	Knapsack	State = (item, budget); budget is a small integer.
a tree, and “choose nodes subject to a rule about neighbours”	Tree	Fix the root’s choice; children become independent subproblems.
a tree, and “for every node as root…”	Tree + rerooting	Two passes: down then up.

How it works

Interval DP

1. State: dp[i][j] = best answer for the range i..j.
2. Transition: try every split point k (or every “last” element) and combine dp[i][k] and dp[k+1][j] with the cost of the final step.
3. Base: ranges of length 1 (or 0).
4. Order: by length, shortest first, so both halves are ready. Row-by-row would read cells that aren’t filled yet.
5. Answer: dp[0][n−1]. Store the best k to reconstruct.

Python

matrix_chain.py

def matrix_chain(dims: list[int]) -> int:
    """Fewest scalar multiplications to multiply M0..M(n-1), where Mk is dims[k] x dims[k+1]."""
    n = len(dims) - 1
    # 1. state: cost[i][j] = cheapest way to multiply Mi..Mj. 3. base: cost[i][i] = 0
    cost = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):              # 4. order: by interval length, shortest first
        for i in range(n - length + 1):
            j = i + length - 1
            # 2. transition: the LAST multiplication splits the chain after some Mk
            cost[i][j] = min(
                cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                for k in range(i, j)
            )
    return cost[0][n - 1] if n else 0           # 5. answer: the whole chain


if __name__ == "__main__":
    assert matrix_chain([10, 30, 5, 60]) == 4500          # (M0 M1) M2
    assert matrix_chain([40, 20, 30, 10, 30]) == 26000
    assert matrix_chain([30, 35, 15, 5, 10, 20, 25]) == 15125  # CLRS 15.2
    assert matrix_chain([5, 7]) == 0                      # one matrix: nothing to do
    print("ok")

TypeScript

matrix_chain.ts

import assert from "node:assert/strict";

/** Fewest scalar multiplications to multiply M0..M(n-1), where Mk is dims[k] x dims[k+1]. */
export function matrixChain(dims: number[]): number {
  const n = dims.length - 1;
  // 1. state: cost[i][j] = cheapest way to multiply Mi..Mj. 3. base: cost[i][i] = 0
  const cost = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let len = 2; len <= n; len++) { // 4. order: by interval length, shortest first
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      cost[i][j] = Infinity;
      for (let k = i; k < j; k++) { // 2. transition: the LAST multiplication splits after Mk
        const c = cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
        if (c < cost[i][j]) cost[i][j] = c;
      }
    }
  }
  return n > 0 ? cost[0][n - 1] : 0; // 5. answer: the whole chain
}

assert.equal(matrixChain([10, 30, 5, 60]), 4500); // (M0 M1) M2
assert.equal(matrixChain([40, 20, 30, 10, 30]), 26000);
assert.equal(matrixChain([30, 35, 15, 5, 10, 20, 25]), 15125); // CLRS 15.2
assert.equal(matrixChain([5, 7]), 0); // one matrix: nothing to do
console.log("ok");

C#

matrix_chain.cs

// Fewest scalar multiplications to multiply M0..M(n-1), where Mk is dims[k] x dims[k+1].
static long MatrixChain(int[] dims)
{
    int n = dims.Length - 1;
    // 1. state: cost[i, j] = cheapest way to multiply Mi..Mj. 3. base: cost[i, i] = 0
    var cost = new long[Math.Max(n, 1), Math.Max(n, 1)];
    for (int len = 2; len <= n; len++)          // 4. order: by interval length, shortest first
        for (int i = 0; i + len - 1 < n; i++)
        {
            int j = i + len - 1;
            cost[i, j] = long.MaxValue;
            for (int k = i; k < j; k++)         // 2. transition: the LAST multiplication splits after Mk
            {
                long c = cost[i, k] + cost[k + 1, j] + (long)dims[i] * dims[k + 1] * dims[j + 1];
                cost[i, j] = Math.Min(cost[i, j], c);
            }
        }
    return n > 0 ? cost[0, n - 1] : 0;          // 5. answer: the whole chain
}

if (MatrixChain([10, 30, 5, 60]) != 4500) throw new Exception("expected 4500");
if (MatrixChain([40, 20, 30, 10, 30]) != 26000) throw new Exception("expected 26000");
if (MatrixChain([30, 35, 15, 5, 10, 20, 25]) != 15125) throw new Exception("expected 15125");
if (MatrixChain([5, 7]) != 0) throw new Exception("expected 0");
Console.WriteLine("ok");

Bitmask DP

1. State: dp[mask][j] where mask is a set (bit k set means item k is included / visited) plus whatever else matters (here, the current city).
2. Transition: add one element not in mask: mask | (1 << k).
3. Base: the smallest mask (here {0}, mask 1).
4. Order: increasing mask; adding a bit always yields a larger number.
5. Answer: from the full mask (1 << n) − 1.

Python

shortest_tour.py

def shortest_tour(dist: list[list[int]]) -> int:
    """Travelling salesman by bitmask DP (Held-Karp): start and end at city 0. O(2^n * n^2)."""
    n = len(dist)
    INF = float("inf")
    # 1. state: best[mask][j] = shortest path from 0 that visits exactly the cities in
    #    mask (bit k set = city k visited) and currently stands on j
    best = [[INF] * n for _ in range(1 << n)]
    best[1][0] = 0                                       # 3. base: only city 0, standing on it
    for mask in range(1 << n):                           # 4. order: adding a bit makes mask bigger
        for j in range(n):
            if best[mask][j] == INF:
                continue
            for k in range(n):                           # 2. transition: go to an unvisited k
                if not mask & (1 << k):
                    nxt = mask | (1 << k)
                    best[nxt][k] = min(best[nxt][k], best[mask][j] + dist[j][k])
    full = (1 << n) - 1
    return int(min(best[full][j] + dist[j][0] for j in range(n)))  # 5. close the loop


if __name__ == "__main__":
    d = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
    assert shortest_tour(d) == 80                        # 0 -> 1 -> 3 -> 2 -> 0
    assert shortest_tour([[0, 2], [2, 0]]) == 4
    assert shortest_tour([[0]]) == 0
    print("ok")

TypeScript

shortest_tour.ts

import assert from "node:assert/strict";

/** Travelling salesman by bitmask DP (Held-Karp): start and end at city 0. O(2^n * n^2). */
export function shortestTour(dist: number[][]): number {
  const n = dist.length;
  // 1. state: best[mask][j] = shortest path from 0 that visits exactly the cities in
  //    mask (bit k set = city k visited) and currently stands on j
  const best = Array.from({ length: 1 << n }, () => new Array<number>(n).fill(Infinity));
  best[1][0] = 0; // 3. base: only city 0, standing on it
  for (let mask = 0; mask < 1 << n; mask++) { // 4. order: adding a bit makes mask bigger
    for (let j = 0; j < n; j++) {
      if (best[mask][j] === Infinity) continue;
      for (let k = 0; k < n; k++) { // 2. transition: go to an unvisited k
        if (mask & (1 << k)) continue;
        const nxt = mask | (1 << k);
        best[nxt][k] = Math.min(best[nxt][k], best[mask][j] + dist[j][k]);
      }
    }
  }
  const full = (1 << n) - 1;
  return Math.min(...best[full].map((v, j) => v + dist[j][0])); // 5. close the loop
}

const d = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]];
assert.equal(shortestTour(d), 80); // 0 -> 1 -> 3 -> 2 -> 0
assert.equal(shortestTour([[0, 2], [2, 0]]), 4);
assert.equal(shortestTour([[0]]), 0);
console.log("ok");

C#

shortest_tour.cs

// Travelling salesman by bitmask DP (Held-Karp): start and end at city 0. O(2^n * n^2).
static int ShortestTour(int[][] dist)
{
    int n = dist.Length;
    const int Inf = int.MaxValue / 2;           // headroom so Inf + d doesn't overflow
    // 1. state: best[mask, j] = shortest path from 0 that visits exactly the cities in
    //    mask (bit k set = city k visited) and currently stands on j
    var best = new int[1 << n, n];
    for (int m = 0; m < 1 << n; m++)
        for (int j = 0; j < n; j++) best[m, j] = Inf;
    best[1, 0] = 0;                             // 3. base: only city 0, standing on it
    for (int mask = 0; mask < 1 << n; mask++)   // 4. order: adding a bit makes mask bigger
        for (int j = 0; j < n; j++)
        {
            if (best[mask, j] == Inf) continue;
            for (int k = 0; k < n; k++)         // 2. transition: go to an unvisited k
            {
                if ((mask & (1 << k)) != 0) continue;
                int nxt = mask | (1 << k);
                best[nxt, k] = Math.Min(best[nxt, k], best[mask, j] + dist[j][k]);
            }
        }
    int full = (1 << n) - 1, answer = Inf;
    for (int j = 0; j < n; j++) answer = Math.Min(answer, best[full, j] + dist[j][0]); // 5. close the loop
    return answer;
}

int[][] d = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]];
if (ShortestTour(d) != 80) throw new Exception("expected 80");
if (ShortestTour([[0, 2], [2, 0]]) != 4) throw new Exception("expected 4");
if (ShortestTour([[0]]) != 0) throw new Exception("expected 0");
Console.WriteLine("ok");

Bit tricks you'll use

mask & (1 << k) tests bit k; mask | (1 << k) adds k; mask & ~(1 << k) removes it; (1 << n) − 1 is the full set. To loop over all submasks of mask: s = mask; while s: …; s = (s − 1) & mask. Over all masks that costs O(3ⁿ) in total, not O(4ⁿ). See bit manipulation.

Knapsack

State (item index, capacity left); transition “skip the item” or “take it”. The knapsack page has the tables, the 0/1 vs unbounded distinction, and why the 1-D loop direction matters.

Tree DP

1. State: for each node v, one value per “fact about v” that the parent needs (picked / not picked, or the best path going down).
2. Transition: combine the children’s values. Children don’t interact once v’s fact is fixed.
3. Base: leaves.
4. Order: post-order (children before parents). Use an explicit stack in Python for deep trees.
5. Answer: at the root, e.g. min(take[root], skip[root]).

Python

min_vertex_cover.py

def min_vertex_cover(n: int, edges: list[tuple[int, int]]) -> int:
    """Fewest nodes so every edge of a tree has at least one chosen endpoint."""
    if n == 0:
        return 0
    adj: list[list[int]] = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    # 4. order: children before parents. An explicit stack avoids Python's recursion limit.
    order, parent, stack = [], [-1] * n, [0]
    seen = [False] * n
    seen[0] = True
    while stack:
        v = stack.pop()
        order.append(v)
        for w in adj[v]:
            if not seen[w]:
                seen[w], parent[w] = True, v
                stack.append(w)
    # 1. state: take[v] / skip[v] = best cover of v's subtree with v in / not in it
    take, skip = [1] * n, [0] * n                # 3. base: a leaf costs 1 or 0
    for v in reversed(order):                    # reversed DFS preorder = children first
        p = parent[v]
        if p >= 0:                               # 2. transition, pushed up to the parent:
            take[p] += min(take[v], skip[v])     #    parent taken: child is free to choose
            skip[p] += take[v]                   #    parent skipped: child must cover the edge
    return min(take[0], skip[0])                 # 5. answer at the root


if __name__ == "__main__":
    assert min_vertex_cover(1, []) == 0
    assert min_vertex_cover(6, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]) == 3  # a path
    assert min_vertex_cover(6, [(0, i) for i in range(1, 6)]) == 1            # a star
    assert min_vertex_cover(7, [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]) == 2
    print("ok")

TypeScript

min_vertex_cover.ts

import assert from "node:assert/strict";

/** Fewest nodes so every edge of a tree has at least one chosen endpoint. */
export function minVertexCover(n: number, edges: [number, number][]): number {
  if (n === 0) return 0;
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  // 1. state: take[v] / skip[v] = best cover of v's subtree with v in / not in it
  const take = new Array<number>(n).fill(1); // 3. base: a leaf costs 1 or 0
  const skip = new Array<number>(n).fill(0);
  const dfs = (v: number, parent: number): void => {
    for (const w of adj[v]) {
      if (w === parent) continue;
      dfs(w, v); // 4. order: solve the child's subtree first
      take[v] += Math.min(take[w], skip[w]); // 2. v taken: child is free to choose
      skip[v] += take[w]; //    v skipped: child must cover the edge
    }
  };
  dfs(0, -1);
  return Math.min(take[0], skip[0]); // 5. answer at the root
}

assert.equal(minVertexCover(1, []), 0);
assert.equal(minVertexCover(6, [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]), 3); // a path
assert.equal(minVertexCover(6, [1, 2, 3, 4, 5].map((i): [number, number] => [0, i])), 1); // a star
assert.equal(minVertexCover(7, [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]), 2);
console.log("ok");

C#

min_vertex_cover.cs

// Fewest nodes so every edge of a tree has at least one chosen endpoint.
static int MinVertexCover(int n, (int A, int B)[] edges)
{
    if (n == 0) return 0;
    var adj = new List<int>[n];
    for (int i = 0; i < n; i++) adj[i] = [];
    foreach (var (a, b) in edges) { adj[a].Add(b); adj[b].Add(a); }
    // 1. state: take[v] / skip[v] = best cover of v's subtree with v in / not in it
    var take = new int[n];
    var skip = new int[n];
    void Dfs(int v, int parent)
    {
        take[v] = 1; skip[v] = 0;                       // 3. base: a leaf costs 1 or 0
        foreach (int w in adj[v])
        {
            if (w == parent) continue;
            Dfs(w, v);                                  // 4. order: solve the child first
            take[v] += Math.Min(take[w], skip[w]);      // 2. v taken: child is free to choose
            skip[v] += take[w];                         //    v skipped: child must cover the edge
        }
    }
    Dfs(0, -1);
    return Math.Min(take[0], skip[0]);                  // 5. answer at the root
}

if (MinVertexCover(1, []) != 0) throw new Exception("expected 0");
if (MinVertexCover(6, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]) != 3) throw new Exception("path: 3");
if (MinVertexCover(6, [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]) != 1) throw new Exception("star: 1");
if (MinVertexCover(7, [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]) != 2) throw new Exception("expected 2");
Console.WriteLine("ok");

What it costs

Shape	States	Work per state	Total time	Typical limit
Interval (try every split)	O(n²)	O(n)	O(n³)	n ≤ ~500
Interval (constant choices, e.g. take left or right end)	O(n²)	O(1)	O(n²)	n ≤ ~5,000
Bitmask (set + current element)	O(2ⁿ · n)	O(n)	O(2ⁿ · n²)	n ≤ ~16-20
Bitmask over submasks			O(3ⁿ)	n ≤ ~15
Knapsack	O(n · W)	O(1)	O(n · W)	W ≤ ~10⁶-10⁷
Tree	O(n · k) for k facts per node	O(children)	O(n · k)	n ≤ 10⁶

Bitmask DP is still exponential, just much less so than brute force: for n = 15, 15! ≈ 1.3 × 10¹² orderings vs 2¹⁵ · 15² ≈ 7.4 × 10⁶ steps. Knapsack is “pseudo-polynomial”: polynomial in the value of W, exponential in its number of digits.

How fast does work grow?

drag n

O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)

n = 16

O(n²): 256 opsO(2ⁿ): 65.5k ops

Variations you’ll meet

• Interval: optimal binary search tree, burst balloons (choose the last element in the range, not the first), stone merging, minimum score triangulation of a polygon, games where two players take from either end.
• Bitmask: travelling salesman, assigning n workers to n jobs, covering all required skills with the fewest people, counting Hamiltonian paths, counting perfect matchings in a small graph.
• Knapsack: 0/1, unbounded, bounded (k copies), multi-dimensional budgets, counting the ways.
• Tree: maximum independent set, vertex cover, tree diameter, “sum of distances to all nodes” (rerooting), DP on a DAG in topological order (the general version of tree DP).
• Digit DP: count numbers ≤ N with some digit property; state = (position, tight flag, extra info). Another “state carries a small flag” pattern.

Pitfalls

• Wrong fill order in interval DP. Row-major order reads dp[k+1][j] before it’s computed. Iterate by length, or iterate i downward and j upward.
• Off-by-one in split points. Is the split [i..k] + [k+1..j] or [i..k−1] + k + [k+1..j] (when k is the element processed last)? Write it down for a length-2 range.
• Bitmask n too large. 2³⁰ states × 30 is 3 × 10¹⁰: too slow and too much memory. If n > ~22, look for a different idea (meet in the middle, or a polynomial algorithm).
• Operator precedence with bits. In C-family languages mask & 1 << k == 0 parses badly. Parenthesise: (mask & (1 << k)) == 0.
• Recursion depth in tree DP. A path-shaped tree of 10⁵ nodes overflows Python’s default stack; use an iterative post-order.
• Re-rooting by brute force. Running a tree DP from every root is O(n²). The two-pass rerooting technique is O(n).

In the interview

• Name the shape early: “This is interval DP: the last merge splits the range in two.” or “n is at most 16, so I can afford a bitmask of the visited set.” The constraint n ≤ 20 is often a deliberate hint.
• Define the state including every piece of information the future depends on (current city, tight flag, parent’s choice). Missing one is the usual bug.
• Justify the order: “by length, because both halves are shorter”.
• Give the state count × work per state as your complexity, then sanity-check against the limits.
• Expect: “reconstruct the choice”, “now it’s a DAG not a tree”, “n doubled”, “what’s the memory?” (bitmask tables can be large: 2²⁰ × 20 ints ≈ 80 MB).

Check yourself

Check yourself

pick one

An interval DP is filled with `for i in range(n): for j in range(i, n):`, reading dp[i][k] and dp[k+1][j]. What goes wrong?

ANothing, row-major order always worksBdp[k+1][j] is in a later row, so it has not been computed yetCIt uses too much memory

Check yourself

pick one

A bitmask DP over n = 20 items with state (mask, last) and O(n) transitions. Roughly how many operations?

AAbout 400BAbout 4 × 10⁸CAbout 2.4 × 10¹⁸ (20!)

Check yourself

pick one

In the vertex cover tree DP, why is skip[v] = Σ take[child] rather than Σ min(take, skip)?

ABecause skipping is cheaperBIf v is not picked, each edge (v, child) must be covered by the child, so every child must be pickedCBecause leaves must always be picked

Practice on your own

Classic exercises (not gym questions):

• Minimum cost to cut a stick at given positions (interval DP).
• Two players take coins from either end of a row; can the first player guarantee at least half? (interval DP with a game twist)
• Assign n ≤ 15 tasks to n workers with a cost matrix, minimising total cost (bitmask DP).
• Maximum independent set in a tree, then with node weights (tree DP).
• Count integers in [1, N] whose digits sum to a multiple of 7 (digit DP).

Go deeper

• Introduction to Algorithms (CLRS), §15.2 “Matrix-chain multiplication” (§14.2 in the 4th edition), the interval-DP prototype.
• cp-algorithms: DP on submasks and the O(3ⁿ) argument.
• Held, M. and Karp, R. M. (1962), “A Dynamic Programming Approach to Sequencing Problems”, J. SIAM 10(1), the original bitmask TSP.
• Competitive Programmer’s Handbook (Laaksonen), ch. 10 “Bit manipulation” (DP over subsets) and ch. 14 “Tree algorithms” (DP on trees).

Related

KnapsackThe (item, budget) shape in full.

Bit manipulationMasks, submask loops and bit tricks.

MemoizationOften the easiest way to write interval and tree DP.

Depth-first searchPost-order traversal for tree DP.