Skip to content

Advanced Dynamic Programming

Overview

This chapter introduces advanced dynamic programming techniques beyond the basics, including tree DP, bitmask DP, digit DP, probability/expectation DP, game-theoretic DP, and DP optimization methods. Each topic is accompanied by classic problems and solution strategies.

1. Tree DP

1.1 Basic Idea

Perform DP on a rooted tree, define states on subtrees, and merge child node information in a bottom-up fashion.

1.2 Classic Problem: Maximum Independent Set on a Tree

Given a tree with \(n\) nodes, select as many nodes as possible such that no two selected nodes are adjacent.

State definition:

  • \(dp[v][0]\): Size of the maximum independent set in the subtree rooted at \(v\) when \(v\) is not selected
  • \(dp[v][1]\): Size of the maximum independent set in the subtree rooted at \(v\) when \(v\) is selected

Transition equations:

\[ dp[v][0] = \sum_{u \in \text{children}(v)} \max(dp[u][0], dp[u][1]) \]
\[ dp[v][1] = 1 + \sum_{u \in \text{children}(v)} dp[u][0] \]
def tree_max_independent_set(adj, root=0):
    """Maximum independent set on a tree"""
    n = len(adj)
    dp = [[0, 0] for _ in range(n)]
    visited = [False] * n

    # Post-order traversal (DFS)
    stack = [(root, False)]
    parent = [-1] * n
    order = []
    visited[root] = True

    while stack:
        v, processed = stack.pop()
        if processed:
            order.append(v)
            continue
        stack.append((v, True))
        for u in adj[v]:
            if not visited[u]:
                visited[u] = True
                parent[u] = v
                stack.append((u, False))

    for v in order:
        dp[v][1] = 1
        for u in adj[v]:
            if u != parent[v]:
                dp[v][0] += max(dp[u][0], dp[u][1])
                dp[v][1] += dp[u][0]

    return max(dp[root][0], dp[root][1])

1.3 Tree Diameter

Two-BFS method: BFS from an arbitrary node to find the farthest node \(u\), then BFS from \(u\) to find the farthest node \(v\); \(d(u,v)\) is the diameter.

Tree DP method:

\[ \text{diameter} = \max_{v} \left( \text{longest\_chain}(v) + \text{second\_longest\_chain}(v) \right) \]
def tree_diameter(adj, root=0):
    """Tree diameter via tree DP"""
    n = len(adj)
    depth1 = [0] * n  # Longest chain
    depth2 = [0] * n  # Second longest chain
    diameter = 0

    # Post-order traversal
    # ... (similar DFS as above)

    for v in order:
        for u in adj[v]:
            if u != parent[v]:
                d = depth1[u] + 1
                if d > depth1[v]:
                    depth2[v] = depth1[v]
                    depth1[v] = d
                elif d > depth2[v]:
                    depth2[v] = d
        diameter = max(diameter, depth1[v] + depth2[v])

    return diameter

1.4 Rerooting DP

Sometimes we need the answer "when each node is the root."

Technique: First perform a standard DP with one fixed root, then transfer answers through parent-child relationships (rerooting) in \(O(n)\) to obtain answers for all roots.

2. Bitmask DP

2.1 Basic Idea

When a problem involves the state of a set, use binary bits to represent the selection status of elements in the set.

State space: \(2^n\) (\(n\) is the set size, typically \(n \leq 20\)).

2.2 Classic Problem: Traveling Salesman Problem (TSP)

Given \(n\) cities and a distance matrix, find the shortest tour that visits every city exactly once and returns to the starting city.

State definition:

  • \(dp[S][i]\): Shortest path length when the set of visited cities is \(S\) and the current city is \(i\)

Transition equation:

\[ dp[S][i] = \min_{j \in S, j \neq i} \left\{ dp[S \setminus \{i\}][j] + d(j, i) \right\} \]

Initial condition: \(dp[\{0\}][0] = 0\)

Answer: \(\min_{i} \left\{ dp[\text{ALL}][i] + d(i, 0) \right\}\)

def tsp_bitmask(dist):
    """Bitmask DP for TSP"""
    n = len(dist)
    INF = float('inf')
    ALL = (1 << n) - 1
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # Start from city 0

    for S in range(1, 1 << n):
        for i in range(n):
            if dp[S][i] == INF:
                continue
            if not (S >> i & 1):
                continue
            for j in range(n):
                if S >> j & 1:  # j already in S
                    continue
                new_S = S | (1 << j)
                dp[new_S][j] = min(dp[new_S][j], dp[S][i] + dist[i][j])

    return min(dp[ALL][i] + dist[i][0] for i in range(n))

Time complexity: \(O(2^n \cdot n^2)\)

Space complexity: \(O(2^n \cdot n)\)

2.3 Classic Problem: Subset Enumeration

Enumerate all subsets of set \(S\):

# Enumerate all non-empty subsets of S
sub = S
while sub > 0:
    # Process subset sub
    process(sub)
    sub = (sub - 1) & S

Total enumeration count: \(\sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n\)

2.4 Classic Problem: Assignment Problem

Assign \(n\) tasks to \(n\) people, each person exactly one task, minimizing total cost.

\[ dp[S] = \min_{j \in S} \left\{ dp[S \setminus \{j\}] + \text{cost}[|S|-1][j] \right\} \]

where \(|S|\) denotes the number of people already assigned.

3. Digit DP

3.1 Basic Idea

Digit DP is used to count integers satisfying specific digit properties (within range \([0, N]\) or \([L, R]\)).

Core elements:

  • Determine digits position by position
  • Maintain a tight flag (whether constrained by the upper bound)
  • May need a leading_zero flag

3.2 General Framework

from functools import lru_cache

def count(N):
    """Count integers in [0, N] satisfying the condition"""
    digits = list(map(int, str(N)))
    n = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight, state):
        """
        pos: current digit position
        tight: whether constrained by the upper bound
        state: problem-specific state
        """
        if pos == n:
            return 1 if is_valid(state) else 0

        limit = digits[pos] if tight else 9
        result = 0
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            new_state = update_state(state, d)
            result += dp(pos + 1, new_tight, new_state)

        return result

    return dp(0, True, initial_state)

3.3 Classic Problem: Count Occurrences of Digit 1 in \([1, N]\)

State: \((pos, tight, count\_of\_1)\)

\[ dp[pos][tight][cnt] = \sum_{d=0}^{\text{limit}} dp[pos+1][\text{new\_tight}][cnt + [d=1]] \]

3.4 Classic Problem: Integers in \([L, R]\) Without Adjacent Identical Digits

State: \((pos, tight, last\_digit, leading\_zero)\)

def count_no_adjacent(N):
    digits = list(map(int, str(N)))
    n = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight, last, leading_zero):
        if pos == n:
            return 1

        limit = digits[pos] if tight else 9
        result = 0
        for d in range(0, limit + 1):
            if not leading_zero and d == last:
                continue  # Skip adjacent identical digits
            new_lz = leading_zero and (d == 0)
            new_last = -1 if new_lz else d
            result += dp(pos + 1, tight and (d == limit), new_last, new_lz)

        return result

    return dp(0, True, -1, True)

4. Probability / Expectation DP

4.1 Basic Idea

States represent probabilities or expected values, and transition equations include probability weights.

Common pattern for expectation DP:

\[ E[v] = \sum_{u} p(v \to u) \cdot (E[u] + \text{cost}(v, u)) \]

4.2 Classic Problem: Coupon Collector Problem

\(n\) types of coupons, each obtained with equal probability. What is the expected number of draws to collect all types?

State: \(dp[i]\) = expected draws to go from \(i\) types to \(i+1\) types.

\[ dp[i] = \frac{n}{n - i} \]

Total expectation:

\[ E = \sum_{i=0}^{n-1} dp[i] = \sum_{i=0}^{n-1} \frac{n}{n-i} = n \sum_{k=1}^{n} \frac{1}{k} = n \cdot H_n \]

4.3 Classic Problem: Random Walk

Expected number of steps from a source to a destination on a graph.

State: \(E[v]\) = expected number of steps from \(v\) to the destination.

Transition:

\[ E[v] = 1 + \frac{1}{\deg(v)} \sum_{u \in N(v)} E[u] \]

For destination \(t\): \(E[t] = 0\).

This is a system of linear equations, solvable by Gaussian elimination.

4.4 Classic Problem: Probability DP

On a DAG, the probability that the sum of edge weights along a path from \(s\) to \(t\) exceeds \(W\).

State: \(p[v][w]\) = probability of reaching \(t\) from \(v\) with remaining budget \(w\).

5. Game-Theoretic DP

5.1 Sprague-Grundy Theorem

Core idea: Any impartial two-player finite game is equivalent to a Nim game.

Grundy value (SG value):

\[ \text{SG}(v) = \text{mex}\{\ \text{SG}(u) \mid u \text{ is a successor state of } v\} \]

where \(\text{mex}(S)\) is the smallest non-negative integer not in \(S\).

  • \(\text{SG}(v) = 0\): Losing position (second player wins)
  • \(\text{SG}(v) > 0\): Winning position (first player wins)

5.2 Nim Game

\(n\) piles of stones with counts \(a_1, a_2, \ldots, a_n\). Two players take turns removing any number of stones from a single pile. The player who takes the last stone wins.

Bouton's theorem: The first player wins if and only if:

\[ a_1 \oplus a_2 \oplus \cdots \oplus a_n \neq 0 \]

where \(\oplus\) denotes the XOR operation.

def nim_winner(piles):
    """Nim game: returns whether the first player wins"""
    xor_sum = 0
    for p in piles:
        xor_sum ^= p
    return xor_sum != 0

5.3 Applications of the SG Theorem

Combination of multiple independent sub-games:

\[ \text{SG}(G_1 + G_2 + \cdots + G_n) = \text{SG}(G_1) \oplus \text{SG}(G_2) \oplus \cdots \oplus \text{SG}(G_n) \]

Example: Multi-pile stone game where at most \(k\) stones can be taken per turn:

\[ \text{SG}(n) = n \mod (k + 1) \]

5.4 Classic Game DP Problem

Coin game: \(n\) coins in a row with values \(v_1, \ldots, v_n\). Two players take turns picking a coin from either end, maximizing their own total value.

State: \(dp[i][j]\) = maximum value the first player can obtain when coins \(v_i, \ldots, v_j\) remain.

\[ dp[i][j] = \max\left(v_i + \min(dp[i+2][j], dp[i+1][j-1]), \; v_j + \min(dp[i+1][j-1], dp[i][j-2])\right) \]

Or more concisely:

\[ dp[i][j] = \text{sum}(i,j) - \min(dp[i+1][j], dp[i][j-1]) \]

where \(\text{sum}(i,j) = v_i + \cdots + v_j\).

6. DP Optimization

6.1 Convex Hull Trick

Applicable when the transition equation has the form:

\[ dp[i] = \min_{j < i} \{dp[j] + b[j] \cdot a[i]\} \]

where \(b[j]\) is monotone and \(a[i]\) is monotone.

Idea: View each \(j\) as a line \(y = b[j] \cdot x + dp[j]\), maintain a lower convex hull, and query the minimum at \(x = a[i]\).

class ConvexHullTrick:
    """Convex hull trick (slopes monotonically decreasing, query points monotonically increasing)"""
    def __init__(self):
        self.lines = []  # [(slope, intercept)]
        self.ptr = 0

    def bad(self, l1, l2, l3):
        """Is l2 dominated by l1 and l3?"""
        return (l3[1] - l1[1]) * (l1[0] - l2[0]) <= (l2[1] - l1[1]) * (l1[0] - l3[0])

    def add_line(self, slope, intercept):
        line = (slope, intercept)
        while len(self.lines) >= 2 and self.bad(self.lines[-2], self.lines[-1], line):
            self.lines.pop()
        self.lines.append(line)

    def query(self, x):
        """Query minimum at x (use pointer when x is monotonically increasing)"""
        while self.ptr < len(self.lines) - 1:
            if self.lines[self.ptr][0] * x + self.lines[self.ptr][1] > \
               self.lines[self.ptr + 1][0] * x + self.lines[self.ptr + 1][1]:
                self.ptr += 1
            else:
                break
        return self.lines[self.ptr][0] * x + self.lines[self.ptr][1]

Time complexity: Amortized \(O(n)\) (monotone case), \(O(n \log n)\) (non-monotone, requires binary search).

6.2 Divide and Conquer Optimization

Applicable when the transition equation is:

\[ dp[i][j] = \min_{k \leq j} \{dp[i-1][k-1] + C(k, j)\} \]

where the optimal decision point \(opt[i][j]\) satisfies monotonicity: \(opt[i][j] \leq opt[i][j+1]\).

Condition: The cost function \(C\) satisfies the quadrangle inequality:

\[ C(a, c) + C(b, d) \leq C(a, d) + C(b, c) \quad (a \leq b \leq c \leq d) \]

Divide and conquer implementation:

def solve(dp_prev, dp_curr, lo, hi, opt_lo, opt_hi, cost):
    """Divide and conquer DP optimization"""
    if lo > hi:
        return

    mid = (lo + hi) // 2
    best_k = opt_lo
    best_val = float('inf')

    for k in range(opt_lo, min(mid, opt_hi) + 1):
        val = dp_prev[k - 1] + cost(k, mid) if k > 0 else cost(0, mid)
        if val < best_val:
            best_val = val
            best_k = k

    dp_curr[mid] = best_val

    solve(dp_prev, dp_curr, lo, mid - 1, opt_lo, best_k, cost)
    solve(dp_prev, dp_curr, mid + 1, hi, best_k, opt_hi, cost)

Time complexity: \(O(kn \log n)\) (\(k\) layers, \(n\) states).

6.3 Slope Optimization

Essentially a generalization of the convex hull trick. Rewrite the transition equation as:

\[ dp[j] = dp[i] + \text{(expression involving } i \text{ and } j\text{)} \]

Transform into a geometric problem involving points \((x_i, y_i)\) and query slopes \(k_j\).

6.4 Knuth's Optimization

Applicable to problems of the optimal binary search tree type:

\[ dp[i][j] = \min_{i \leq k \leq j} \{dp[i][k-1] + dp[k+1][j]\} + w(i, j) \]

Knuth's theorem: If \(w\) satisfies the quadrangle inequality, then \(opt[i][j-1] \leq opt[i][j] \leq opt[i+1][j]\).

By exploiting the monotonicity of optimal decision points, \(O(n^3)\) can be reduced to \(O(n^2)\).

7. DP Optimization Summary

Optimization Method Applicable Condition Complexity Improvement
Convex Hull Trick Linear transition, monotone slopes/queries \(O(n^2) \to O(n)\)
Divide and Conquer Monotone decision points \(O(kn^2) \to O(kn\log n)\)
Knuth's Optimization Interval DP + quadrangle inequality \(O(n^3) \to O(n^2)\)
Slope Optimization Linearizable transition \(O(n^2) \to O(n)\) or \(O(n\log n)\)
Data Structure Optimization Range query/update Depends on structure 
graph TD
    DP[DP Optimization] --> CHT[Convex Hull Trick]
    DP --> DC[Divide and Conquer]
    DP --> KNUTH[Knuth's Optimization]
    DP --> DS[Data Structure Optimization]
    CHT --> CHT1[Monotone slopes: O-n]
    CHT --> CHT2[Non-monotone slopes: O-n-log-n]
    DC --> DC1[Monotone decision points]
    DC --> DC2[Quadrangle inequality]
    KNUTH --> KNUTH1[Interval DP]
    DS --> SEG[Segment Tree]
    DS --> BIT[Binary Indexed Tree]
    DS --> DEQUE[Monotone Queue/Stack]
Type Problem Key Technique
Tree DP Maximum independent set on tree Select/not-select two states
Tree DP Center of tree Rerooting DP
Bitmask DP TSP \(dp[S][i]\), \(O(2^n n^2)\)
Bitmask DP Board covering Row state compression
Digit DP Digit counting \([L,R]\) decomposition
Expectation DP Coupon collector Harmonic series
Game DP Nim game SG theorem
Convex Hull Trick Piecewise linear cost Maintain convex hull
Divide and Conquer \(k\)-segment minimum cost Monotone decision points

References

  • Cormen et al., Introduction to Algorithms (CLRS), Chapters 15-16
  • Competitive Programming 3 (CP3), Chapter 3 & 8
  • Halim & Halim, Competitive Programming
  • OI Wiki (oi-wiki.org)

Related sections:

评论 #