Lesson 5: Advanced Patterns

Tree, Bitmask, & Digit DP

Push your DP skills to the extreme. Learn how to solve complex combinatorial problems on trees, manage subsets with bitmasks, and count numbers efficiently.

80 Minutes

Expert

Tree DP

DP over nodes & subtrees

Bitmask DP

Subset optimizations (TSP)

Digit DP

Counting within ranges

1. Tree DP

Tree DP usually involves a DFS traversal. The state for a node depends on its children.

Example: Independent Set. For each node, we decide:
1. Take the node (cannot take children).
2. Skip the node (can take children).

Key Insight

Complex Tree DP might require "Rerooting" where you compute the answer for every node as a potential root in O(N).

DFS Tree DP Pattern

Pseudocode

1function solve(u, p):
2  // dp[u][0]: Skip u, dp[u][1]: Take u
3  dp[u][0] = 0
4  dp[u][1] = weight[u]
5  
6  for v in adj[u]:
7    if v == p: continue
8    solve(v, u)
9    
10    dp[u][0] += max(dp[v][0], dp[v][1])
11    dp[u][1] += dp[v][0] // Can't take child if u taken

TSP (Travelling Salesman)

Pseudocode

1function TSP(mask, current):
2  if mask == ALL_VISITED: 
3    return dist[current][0]
4    
5  if memo[mask][current]: 
6    return memo[mask][current]
7    
8  res = INF
9  for next in 0..N-1:
10    if !(mask & (1 << next)):
11      cost = dist[current][next] + 
12             TSP(mask | (1 << next), next)
13      res = min(res, cost)
14      
15  return memo[mask][current] = res

2. Bitmask DP

When items are few (~20) and we need to track subsets, we use an integer as a "mask" to represent state. $2^N$ states are manageable for small $N$.

Bitwise Ops

Check: (mask & (1 << i))Set: (mask | (1 << i))

Typical use cases: Matching, TSP, Assignment Problem.

3. Digit DP

Count numbers in range $[L, R]$ satisfying a condition. Instead of checking every number (too slow), we build numbers digit by digit.

The state usually includes:

pos: Current digit position
tight: Are we restricted by the range boundary?
cond: Condition progress (e.g., sum of digits)

Digit DP Pattern

Pseudocode

1function count(idx, tight, sum):
2  if idx == len(num): return sum == K
3  
4  limit = tight ? num[idx] : 9
5  ans = 0
6  
7  for d from 0 to limit:
8    newTight = tight && (d == limit)
9    ans += count(idx + 1, newTight, sum + d)
10    
11  return ans

The DP Problem Atlas

A collection of recurring patterns and classic problems to help you identify the right DP approach instantly.

Optimization Problems Final Summary & Review

1. Tree DP

Key Insight

Complex Tree DP might require "Rerooting" where you compute the answer for every node as a potential root in O(N).

1function solve(u, p): 2 // dp[u][0]: Skip u, dp[u][1]: Take u 3 dp[u][0] = 0 4 dp[u][1] = weight[u] 5 6 for v in adj[u]: 7 if v == p: continue 8 solve(v, u) 9 10 dp[u][0] += max(dp[v][0], dp[v][1]) 11 dp[u][1] += dp[v][0] // Can't take child if u taken

1function TSP(mask, current): 2 if mask == ALL_VISITED: 3 return dist[current][0] 4 5 if memo[mask][current]: 6 return memo[mask][current] 7 8 res = INF 9 for next in 0..N-1: 10 if !(mask & (1 << next)): 11 cost = dist[current][next] + 12 TSP(mask | (1 << next), next) 13 res = min(res, cost) 14 15 return memo[mask][current] = res

3. Digit DP

Count numbers in range $[L, R]$ satisfying a condition. Instead of checking every number (too slow), we build numbers digit by digit.

The state usually includes:

pos: Current digit position
tight: Are we restricted by the range boundary?
cond: Condition progress (e.g., sum of digits)

Digit DP Pattern

Pseudocode

1function count(idx, tight, sum):
2  if idx == len(num): return sum == K
3  
4  limit = tight ? num[idx] : 9
5  ans = 0
6  
7  for d from 0 to limit:
8    newTight = tight && (d == limit)
9    ans += count(idx + 1, newTight, sum + d)
10    
11  return ans