Advanced DP — patterns and use cases

The five advanced DP families that cover most mid-to-hard contest DP: two-sequence/grid prefix DP, interval DP, bitmask DP, digit DP, and tree DP. Each comes with its state signature, when to use it, the feasible constraint range, and a top-down template.

Pattern 1 — Two-sequence / grid prefix DP

State: solve(i, j) — a pair of indices into two sequences (or row/column of a grid). Transition: compare the current pair; either they match (consume both) or you skip one side.

Use when: the problem compares or aligns two sequences — longest common subsequence, edit distance, shortest common supersequence, counting distinct subsequences, regex/wildcard matching.

Size: O(n·m) states, O(1)–O(alphabet) work → feasible for n, m ≤ several thousand.

Template — edit distance (min insert/delete/replace to turn s into t):

int n, m;
string s, t;
int memo[2005][2005];      // init -1

int ed(int i, int j) {
    if (i == n) return m - j;            // insert the rest of t
    if (j == m) return n - i;            // delete the rest of s
    int& r = memo[i][j];
    if (r != -1) return r;
    if (s[i] == t[j]) return r = ed(i + 1, j + 1);     // free match
    return r = 1 + min({ ed(i + 1, j),       // delete s[i]
                         ed(i, j + 1),       // insert t[j]
                         ed(i + 1, j + 1) });// replace
}

LCS is the same skeleton with +1 on a match and max of the two skips. This pattern is the natural generalisation of Part 1's prefix/LIS DP from one sequence to two.

Pattern 2 — Interval DP

State: solve(l, r) — the answer for the contiguous range [l, r]. Transition: either pick a split point k inside the range and combine the two halves, or peel off an endpoint.

Use when: the cost of combining a range depends on how you parenthesise/order operations inside it — matrix chain multiplication, optimal BST, burst balloons, palindrome problems, merging stones, removing boxes.

Size: O(n²) states × O(n) splits → O(n³), so n ≤ ~500.

Split template — matrix chain (min scalar multiplications):

int p[505];                // dims: matrix i is p[i-1] x p[i]
int memo[505][505];        // init -1

int solve(int i, int j) {  // cost to multiply matrices i..j
    if (i == j) return 0;                  // single matrix: nothing to do
    int& r = memo[i][j];
    if (r != -1) return r;
    int best = INT_MAX;
    for (int k = i; k < j; k++)            // try every split
        best = min(best, solve(i, k) + solve(k + 1, j)
                         + p[i - 1] * p[k] * p[j]);
    return r = best;
}

Endpoint template — longest palindromic subsequence: if (s[i]==s[j]) 2 + solve(i+1, j-1) else max(solve(i+1, j), solve(i, j-1)). The key recognition signal: "the answer for a range is built from sub-ranges, and I must choose where to break it."

Pattern 3 — Bitmask DP (subset as state)

State: an integer mask whose bits mark which elements are used/visited, often paired with i = the last element chosen. Transition: add one currently-unused element to the set.

Use when: you must consider all orderings or subsets of a small set — travelling salesman, assignment (match n people to n tasks), Hamiltonian paths, set cover, "partition into groups" where n ≤ ~20.

Size: 2ⁿ masks (× n) → only feasible for n ≤ 20ish. That tiny bound in the statement is the giveaway.

Template — TSP (min tour cost visiting all nodes, returning to 0):

int n, dist[20][20];
int memo[1 << 20][20];      // init -1  (watch the memory — see Tips)

int tsp(int mask, int u) {  // mask = visited set, u = current node
    if (mask == (1 << n) - 1) return dist[u][0];   // all visited → go home
    int& r = memo[mask][u];
    if (r != -1) return r;
    int best = INT_MAX;
    for (int v = 0; v < n; v++)
        if (!(mask & (1 << v)))                    // v unvisited
            best = min(best, dist[u][v] + tsp(mask | (1 << v), v));
    return r = best;
}
// answer: tsp(1, 0)   — start at node 0, only 0 visited

Bit tricks you'll use constantly: mask & (1<<v) (is v in the set?), mask | (1<<v) (add v), mask & (mask-1) (drop lowest bit), __builtin_popcount(mask) (set size). For assignment-style problems, __builtin_popcount(mask) often is the position index, dropping a dimension.

Pattern 4 — Digit DP (counting numbers)

State: solve(pos, acc, tight) — current digit position, an accumulator for whatever you're tracking (digit sum, remainder, last digit…), and a tight flag meaning "the prefix so far equals the bound's prefix." Transition: try each digit 0..limit, where limit is bound[pos] if still tight, else 9.

Use when: you must count numbers in a range [0, N] (or [A, B] via f(B) - f(A-1)) satisfying a digit property — digit sum divisible by k, no two equal adjacent digits, contains/avoids a digit, etc. N can be astronomically large (up to 10¹⁸) because you work on its ~18 digits, not the value.

Template — count integers in [0, N] with digit sum exactly target:

string num;                // N as a decimal string
int target;
long long memo[20][200][2];   // [pos][sum][tight], init -1

long long go(int pos, int sum, int tight) {
    if (sum > target) return 0;
    if (pos == (int)num.size()) return sum == target;
    long long& r = memo[pos][sum][tight];
    if (r != -1) return r;
    int limit = tight ? num[pos] - '0' : 9;
    long long res = 0;
    for (int d = 0; d <= limit; d++)
        res += go(pos + 1, sum + d, tight && (d == limit));
    return r = res;
}
// answer: go(0, 0, 1)

Leading zeros are harmless here (they add 0 to the sum); some problems need an extra started flag to treat them specially. The accumulator's range sets the memo size — keep it bounded (e.g. track sum % k, not sum, when only divisibility matters).

Pattern 5 — Tree DP (DP on rooted trees)

State: solve(node, status) — the answer for the subtree rooted at node, where status is a tiny tag (e.g. is node itself selected?). Transition: combine the answers of the children, computed by a single DFS.

Use when: the input is a tree (or forest) and the answer aggregates over subtrees — subtree sizes/sums, max-weight independent set, tree diameter, counting matchings, distributing resources, "choose nodes with a parent/child constraint."

Size: O(n) states (or O(n · #statuses)) — linear, because each node is visited once.

Template — maximum-weight independent set (no two adjacent nodes chosen):

vector<int> adj[100005];
int w[100005];
long long dp[100005][2];   // dp[u][0] = u NOT taken, dp[u][1] = u taken

void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = w[u];
    for (int v : adj[u]) if (v != parent) {
        dfs(v, u);                              // solve child subtree first
        dp[u][0] += max(dp[v][0], dp[v][1]);    // u free → child either way
        dp[u][1] += dp[v][0];                   // u taken → child must be free
    }
}
// answer: dfs(root, -1); then max(dp[root][0], dp[root][1])

The DFS post-order is the dependency order — children finish before their parent combines them, so no explicit memo array is needed beyond dp[]. Mind the recursion depth: a path-shaped tree of 10⁵ nodes recurses 10⁵ deep and can overflow the stack (see Tips).

Bonus — bounded knapsack via binary splitting

Part 1 deferred bounded knapsack (item i available exactly cnt[i] times). The clean trick reduces it to the 0/1 knapsack you already know: split each item count into powers of two.

Any count c can be written as 1 + 2 + 4 + … + 2^(k-1) + remainder, and those groups can combine to make any quantity from 0 to c. So replace item i (count c) with O(log c) virtual items of sizes 1, 2, 4, …, each a normal 0/1 item:

// expand (weight w, value v, count c) into binary-grouped 0/1 items
vector<pair<int,int>> items;       // (weight, value)
for (int k = 1; c > 0; k <<= 1) {
    int take = min(k, c);          // group of size 'take'
    items.push_back({ w * take, v * take });
    c -= take;
}
// then run ordinary 0/1 knapsack over `items`

This turns an O(W · Σc) DP into O(W · Σ log c) — the difference between TLE and AC when counts are large. It's the bridge from Part 1's knapsack to the contest-grade version, and a good reminder that a hard DP is often an easy DP after the right reformulation of the items/state.

Pattern cheat sheet

Pattern	State	Signal in the statement	Complexity	Feasible n
2D prefix	`solve(i, j)`	two sequences / a grid	O(n·m)	a few thousand
Interval	`solve(l, r)`	order/parenthesisation of a range	O(n³)	≤ ~500
Bitmask	`solve(mask, i)`	all subsets/orderings, tiny n	O(2ⁿ·n)	≤ ~20
Digit	`solve(pos, acc, tight)`	count numbers ≤ huge N	O(digits·acc)	N ≤ 10¹⁸
Tree	`solve(node, status)`	input is a tree	O(n·status)	10⁵–10⁶

Real problems often compose these — e.g. a tree DP whose per-node state is a small knapsack, or a bitmask over groups with an inner 2D DP. Master each shape in isolation first; the combinations then read as "a DP inside a DP."