Advanced DP — classic problems

Seven advanced DP classics worked end to end as top-down recursion + memoization — longest common subsequence, edit distance, matrix chain multiplication, longest palindromic subsequence, travelling salesman (bitmask), digit-sum counting (digit DP), and tree max-weight independent set.

1. Longest Common Subsequence (LCS) — 2D prefix DP

Problem: given two strings s and t, find the length of the longest subsequence common to both (characters in order, not necessarily contiguous).

State: lcs(i, j) = LCS length of the suffixes s[i..] and t[j..]. Transition: if the front characters match, take both and recurse; otherwise drop one side and take the better:

Example

lcs(i, j) = 1 + lcs(i+1, j+1) if s[i] == t[j]

= max(lcs(i+1, j), lcs(i, j+1)) otherwise

Base: lcs(i, j) = 0 once either string is exhausted (i == n or j == m).

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

int lcs(int i, int j) {
    if (i == n || j == m) return 0;
    int& r = memo[i][j];
    if (r != -1) return r;
    if (s[i] == t[j]) return r = 1 + lcs(i + 1, j + 1);
    return r = max(lcs(i + 1, j), lcs(i, j + 1));
}
// answer: lcs(0, 0)

O(n·m) time and memo. This is the archetype of two-sequence DP — edit distance, shortest common supersequence, and diff tools are all variations of this skeleton.

2. Edit Distance (Levenshtein)

Problem: find the minimum number of single-character insertions, deletions, or replacements to turn s into t.

State: ed(i, j) = min operations to convert s[i..] into t[j..]. Transition: a free move on a match, otherwise pay 1 for the cheapest of the three edits:

Example

ed(i, j) = ed(i+1, j+1) if s[i] == t[j]

= 1 + min( ed(i+1, j), // delete s[i]

ed(i, j+1), // insert t[j]

ed(i+1, j+1) ) // replace s[i] with t[j]

Base: if s is exhausted, insert the rest of t (m - j); if t is exhausted, delete the rest of s (n - i).

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

int ed(int i, int j) {
    if (i == n) return m - j;            // insert remaining t
    if (j == m) return n - i;            // delete remaining s
    int& r = memo[i][j];
    if (r != -1) return r;
    if (s[i] == t[j]) return r = ed(i + 1, j + 1);
    return r = 1 + min({ ed(i + 1, j), ed(i, j + 1), ed(i + 1, j + 1) });
}
// answer: ed(0, 0)

The three recursive calls map one-to-one onto the three edit operations — once you see that, the recurrence writes itself. O(n·m).

3. Matrix Chain Multiplication — interval DP (split)

Problem: given matrix dimensions where matrix i is p[i-1] × p[i], parenthesise the product A₁·A₂·…·Aₙ to minimise the total number of scalar multiplications. (Multiplying an a×b by a b×c matrix costs a·b·c.)

State: solve(i, j) = min cost to multiply matrices i..j. Transition: try every place k to make the last multiplication, splitting [i,j] into [i,k] and [k+1,j]:

Example

solve(i, j) = min over k in [i, j-1] of

solve(i, k) + solve(k+1, j) + p[i-1]·p[k]·p[j]

Base: solve(i, i) = 0 — a single matrix needs no multiplication.

int p[505];                // dims; n matrices
int memo[505][505];        // init to -1

int solve(int i, int j) {
    if (i == j) return 0;
    int& r = memo[i][j];
    if (r != -1) return r;
    int best = INT_MAX;
    for (int k = i; k < j; k++)
        best = min(best, solve(i, k) + solve(k + 1, j) + p[i - 1] * p[k] * p[j]);
    return r = best;
}
// answer: solve(1, n)

O(n²) states × O(n) splits = O(n³). This is the prototype "choose a split point" interval DP; optimal BST, polygon triangulation, and burst-balloons share the structure. Recursion picks the by-length fill order automatically — a real headache to get right bottom-up.

4. Longest Palindromic Subsequence — interval DP (endpoints)

Problem: find the length of the longest subsequence of s that reads the same forwards and backwards.

State: lps(i, j) = length of the longest palindromic subsequence within s[i..j]. Transition: if the two ends match, they wrap a palindrome of the inside (+2); otherwise drop one end:

Example

lps(i, j) = 2 + lps(i+1, j-1) if s[i] == s[j]

= max(lps(i+1, j), lps(i, j-1)) otherwise

Base: lps(i, j) = 0 if i > j (empty), 1 if i == j (single character).

string s;
int memo[1005][1005];      // init to -1

int lps(int i, int j) {
    if (i > j) return 0;
    if (i == j) return 1;
    int& r = memo[i][j];
    if (r != -1) return r;
    if (s[i] == s[j]) return r = 2 + lps(i + 1, j - 1);
    return r = max(lps(i + 1, j), lps(i, j - 1));
}
// answer: lps(0, s.size() - 1)

This is the endpoint flavour of interval DP (peel an end) versus matrix chain's split flavour (break in the middle). Recognising which flavour a problem wants is the main modelling decision. O(n²). (Tip: LPS of s equals LCS of s and its reverse — a neat equivalence.)

5. Travelling Salesman Problem (TSP) — bitmask DP

Problem: given n cities and a distance matrix, find the shortest tour that starts at city 0, visits every city exactly once, and returns to 0. (n ≤ ~20.)

State: tsp(mask, u) = min cost to finish the tour, given the set of visited cities mask and current city u. Transition: go to any unvisited city v:

Example

tsp(mask, u) = min over unvisited v of dist[u][v] + tsp(mask | (1<<v), v)

Base: when mask is full (all bits set), return home: dist[u][0].

int n, dist[20][20];
int memo[1 << 20][20];     // init to -1

int tsp(int mask, int u) {
    if (mask == (1 << n) - 1) return dist[u][0];   // all visited → return to 0
    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)))
            best = min(best, dist[u][v] + tsp(mask | (1 << v), v));
    return r = best;
}
// answer: tsp(1, 0)   — start at city 0, only city 0 visited

O(2ⁿ · n) states × O(n) work = O(2ⁿ · n²). At n = 20 that's ~4×10⁸ — borderline but classic. The memo[1<<20][20] table is the real constraint: ~80 M ints ≈ 320 MB, so in practice you keep n modest or use a flat/short table (see Tips). The same (mask, position) state solves the assignment problem and Hamiltonian-path counting.

6. Digit-sum counting — digit DP

Problem: count how many integers in [0, N] have a digit sum exactly equal to target. N can be enormous (up to 10¹⁸) — far too large to loop over.

Key idea: build the number digit by digit from most significant to least. Carry a tight flag: while tight, the prefix equals N's prefix, so the next digit is capped at N's digit; once you place something smaller, tight releases and all remaining digits range freely 0..9.

State: go(pos, sum, tight) = count of ways to fill positions pos..end so the total digit sum reaches target.

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

long long go(int pos, int sum, int tight) {
    if (sum > target) return 0;                    // prune
    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)        — counts integers in [0, N] (leading zeros add 0)

For a range [A, B], compute f(B) - f(A - 1). The accumulator (sum here) is whatever the property needs — a remainder sum % k for divisibility, the previous digit for adjacency rules, etc. Keep the accumulator's range small, because it multiplies the state count. Runtime is microscopic: ~18 × target × 2 × 10 operations.

7. Tree max-weight independent set — tree DP

Problem: given a tree of n weighted nodes, choose a subset of nodes with no two adjacent (no edge between two chosen nodes) maximising the total weight. (The tree version of house robber.)

State: for each node u, two answers over its subtree — dp[u][0] (u not chosen) and dp[u][1] (u chosen). Transition (post-order DFS):

Example

dp[u][1] = w[u] + Σ dp[child][0] // u chosen ⇒ children excluded

dp[u][0] = Σ max(dp[child][0], dp[child][1]) // u free ⇒ child either way

Base: a leaf has dp[leaf][0] = 0, dp[leaf][1] = w[leaf] (the loop over children simply doesn't run).

vector<int> adj[100005];
int w[100005];
long long dp[100005][2];

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);                               // children first
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}
// answer: dfs(0, -1); then max(dp[0][0], dp[0][1])

O(n) — each node and edge is processed once; the DFS post-order is the dependency order, so no separate memo is needed. This dp[node][status] shape (status = a tiny per-node tag) covers a huge range of tree problems. Caution: a long path-shaped tree recurses n deep — for n = 10⁵–10⁶, raise the stack or convert the DFS to an explicit stack/BFS order (see Tips).

1. Longest Common Subsequence (LCS) — 2D prefix DP

Problem: given two strings s and t, find the length of the longest subsequence common to both (characters in order, not necessarily contiguous).

State: lcs(i, j) = LCS length of the suffixes s[i..] and t[j..]. Transition: if the front characters match, take both and recurse; otherwise drop one side and take the better:

Example

lcs(i, j) = 1 + lcs(i+1, j+1) if s[i] == t[j]

= max(lcs(i+1, j), lcs(i, j+1)) otherwise

Base: lcs(i, j) = 0 once either string is exhausted (i == n or j == m).

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

int lcs(int i, int j) {
    if (i == n || j == m) return 0;
    int& r = memo[i][j];
    if (r != -1) return r;
    if (s[i] == t[j]) return r = 1 + lcs(i + 1, j + 1);
    return r = max(lcs(i + 1, j), lcs(i, j + 1));
}
// answer: lcs(0, 0)

O(n·m) time and memo. This is the archetype of two-sequence DP — edit distance, shortest common supersequence, and diff tools are all variations of this skeleton.

2. Edit Distance (Levenshtein)

Problem: find the minimum number of single-character insertions, deletions, or replacements to turn s into t.

State: ed(i, j) = min operations to convert s[i..] into t[j..]. Transition: a free move on a match, otherwise pay 1 for the cheapest of the three edits:

Example

ed(i, j) = ed(i+1, j+1) if s[i] == t[j]

= 1 + min( ed(i+1, j), // delete s[i]

ed(i, j+1), // insert t[j]

ed(i+1, j+1) ) // replace s[i] with t[j]

Base: if s is exhausted, insert the rest of t (m - j); if t is exhausted, delete the rest of s (n - i).

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

int ed(int i, int j) {
    if (i == n) return m - j;            // insert remaining t
    if (j == m) return n - i;            // delete remaining s
    int& r = memo[i][j];
    if (r != -1) return r;
    if (s[i] == t[j]) return r = ed(i + 1, j + 1);
    return r = 1 + min({ ed(i + 1, j), ed(i, j + 1), ed(i + 1, j + 1) });
}
// answer: ed(0, 0)

The three recursive calls map one-to-one onto the three edit operations — once you see that, the recurrence writes itself. O(n·m).

3. Matrix Chain Multiplication — interval DP (split)

State: solve(i, j) = min cost to multiply matrices i..j. Transition: try every place k to make the last multiplication, splitting [i,j] into [i,k] and [k+1,j]:

Example

solve(i, j) = min over k in [i, j-1] of

solve(i, k) + solve(k+1, j) + p[i-1]·p[k]·p[j]

Base: solve(i, i) = 0 — a single matrix needs no multiplication.

int p[505];                // dims; n matrices
int memo[505][505];        // init to -1

int solve(int i, int j) {
    if (i == j) return 0;
    int& r = memo[i][j];
    if (r != -1) return r;
    int best = INT_MAX;
    for (int k = i; k < j; k++)
        best = min(best, solve(i, k) + solve(k + 1, j) + p[i - 1] * p[k] * p[j]);
    return r = best;
}
// answer: solve(1, n)

4. Longest Palindromic Subsequence — interval DP (endpoints)

Problem: find the length of the longest subsequence of s that reads the same forwards and backwards.

State: lps(i, j) = length of the longest palindromic subsequence within s[i..j]. Transition: if the two ends match, they wrap a palindrome of the inside (+2); otherwise drop one end:

Example

lps(i, j) = 2 + lps(i+1, j-1) if s[i] == s[j]

= max(lps(i+1, j), lps(i, j-1)) otherwise

Base: lps(i, j) = 0 if i > j (empty), 1 if i == j (single character).

string s;
int memo[1005][1005];      // init to -1

int lps(int i, int j) {
    if (i > j) return 0;
    if (i == j) return 1;
    int& r = memo[i][j];
    if (r != -1) return r;
    if (s[i] == s[j]) return r = 2 + lps(i + 1, j - 1);
    return r = max(lps(i + 1, j), lps(i, j - 1));
}
// answer: lps(0, s.size() - 1)

5. Travelling Salesman Problem (TSP) — bitmask DP

Problem: given n cities and a distance matrix, find the shortest tour that starts at city 0, visits every city exactly once, and returns to 0. (n ≤ ~20.)

State: tsp(mask, u) = min cost to finish the tour, given the set of visited cities mask and current city u. Transition: go to any unvisited city v:

Example

tsp(mask, u) = min over unvisited v of dist[u][v] + tsp(mask | (1<<v), v)

Base: when mask is full (all bits set), return home: dist[u][0].

int n, dist[20][20];
int memo[1 << 20][20];     // init to -1

int tsp(int mask, int u) {
    if (mask == (1 << n) - 1) return dist[u][0];   // all visited → return to 0
    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)))
            best = min(best, dist[u][v] + tsp(mask | (1 << v), v));
    return r = best;
}
// answer: tsp(1, 0)   — start at city 0, only city 0 visited

6. Digit-sum counting — digit DP

Problem: count how many integers in [0, N] have a digit sum exactly equal to target. N can be enormous (up to 10¹⁸) — far too large to loop over.

State: go(pos, sum, tight) = count of ways to fill positions pos..end so the total digit sum reaches target.

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

long long go(int pos, int sum, int tight) {
    if (sum > target) return 0;                    // prune
    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)        — counts integers in [0, N] (leading zeros add 0)

7. Tree max-weight independent set — tree DP

Problem: given a tree of n weighted nodes, choose a subset of nodes with no two adjacent (no edge between two chosen nodes) maximising the total weight. (The tree version of house robber.)

State: for each node u, two answers over its subtree — dp[u][0] (u not chosen) and dp[u][1] (u chosen). Transition (post-order DFS):

Example

dp[u][1] = w[u] + Σ dp[child][0] // u chosen ⇒ children excluded

dp[u][0] = Σ max(dp[child][0], dp[child][1]) // u free ⇒ child either way

Base: a leaf has dp[leaf][0] = 0, dp[leaf][1] = w[leaf] (the loop over children simply doesn't run).

vector<int> adj[100005];
int w[100005];
long long dp[100005][2];

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);                               // children first
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}
// answer: dfs(0, -1); then max(dp[0][0], dp[0][1])