Dp Cf Patterns

DP Patterns — Codeforces Style

CF DP is different from LeetCode DP. No "buy and sell stock" or "house robber." You'll see: - DP on trees (DFS + memoization on nodes) - DP on graphs (topological order) - DP with bitmasks (n ≤ 20) - DP with combinatorics (counting ways) - DP optimized with segment trees / Fenwick - Digit DP (counting numbers with property X in range [L, R])

1. Classic CF DP (1D / 2D)

KnapSack-Style (CF staple)

// Given items with weight w[i], find possible sums
dp := make([]bool, MAX_SUM+1)
dp[0] = true
for i := 0; i < n; i++ {
    for s := MAX_SUM; s >= w[i]; s-- {  // reverse to avoid reuse
        dp[s] = dp[s] || dp[s - w[i]]
    }
}

CF Variant: Instead of boolean, store minimum items to reach sum, or maximum value, or is it possible to divide into k groups.

Coin Change Variants

// Minimum coins to make sum
dp := make([]int, SUM+1)
for i := range dp { dp[i] = INF }
dp[0] = 0
for _, c := range coins {
    for s := c; s <= SUM; s++ {
        dp[s] = min(dp[s], dp[s-c] + 1)
    }
}

LIS (Longest Increasing Subsequence) — O(n log n)

tails := []int{}
for _, x := range arr {
    i := sort.SearchInts(tails, x)  // < for strictly increasing, <= for non-decreasing
    if i == len(tails) {
        tails = append(tails, x)
    } else {
        tails[i] = x
    }
}
return len(tails)

2. DP on Trees (CF's bread and butter)

Node dp stores something computed from children.

// Example: Max independent set on tree (no two adjacent nodes selected)
func dfs(u, parent int) {
    dp0 := 0  // not taking u
    dp1 := 1  // taking u
    for _, v := range tree[u] {
        if v == parent { continue }
        dfs(v, u)
        dp0 += max(dp0Child[v], dp1Child[v])
        dp1 += dp0Child[v]  // cannot take child if u is taken
    }
    dp0Child[u], dp1Child[u] = dp0, dp1
}

Common tree DP variants: - Tree diameter (max distance between any 2 nodes) - Tree DP with rerooting (calculate answer for every node as root) - DP for tree distances (sum of distances from each node to all others) - KnapSack on tree (DP[node][capacity] = value)

3. DP with Bitmasks (n ≤ 20)

// Assign n tasks to n people, cost[i][j] = cost to assign task i to person j
// dp[mask] = min cost for assigned tasks in mask
dp := make([]int, 1<<n)
for i := range dp { dp[i] = INF }
dp[0] = 0
for mask := 0; mask < (1 << n); mask++ {
    i := bits.OnesCount(uint(mask))  // next person to assign
    for j := 0; j < n; j++ {
        if mask&(1<<j) == 0 {
            dp[mask|(1<<j)] = min(dp[mask|(1<<j)], dp[mask] + cost[i][j])
        }
    }
}

Key insight: O(n * 2^n) — works for n ≤ 20.

4. DP + Data Structures (Segment Tree Optimization)

When recurrence is: dp[i] = max(dp[j] + f(j, i)) for all j < i: - If f(j, i) is simple (value only depends on j), maintain max dp[j] + something in a segment tree - If f(j, i) = arr[i] — some value from j to i, use prefix sums + segment tree

This is how you solve problems that look O(n²) in O(n log n).

5. Digit DP

Count numbers in range [L, R] with some property (sum of digits ≤ k, no consecutive 1s, etc.)

// Count numbers from 0 to R where sum of digits ≤ k
func digitDP(R int, k int) int {
    digits := strconv.Itoa(R)
    n := len(digits)

    var dfs func(pos int, sum int, tight bool) int
    memo := make([][][]int, n)
    // ... memoization on (pos, sum, tight)

    dfs = func(pos int, sum int, tight bool) int {
        if sum > k { return 0 }
        if pos == n { return 1 }
        if !tight && memo[pos][sum] != -1 { return memo[pos][sum] }

        limit := 9
        if tight { limit = int(digits[pos] - '0') }

        total := 0
        for d := 0; d <= limit; d++ {
            total += dfs(pos+1, sum+d, tight && d == limit)
        }
        if !tight { memo[pos][sum] = total }
        return total
    }
    return dfs(0, 0, true)
}
// Result for [L, R] = solve(R) - solve(L-1)

6. DP Key Insights (CF Specific)

Insight	Example
Forward DP	Instead of "what's best ending at i", try "starting from i, where can I go?"
Reverse DP	DP from end to start when decisions depend on future
DP on permutation	Insertion DP: build permutation by inserting elements one by one
Expected value DP	Often solve from "end state" backwards using linear equations
Convex Hull Trick	When dp[i] = min(dp[j] + a[j]*b[i]) — lines with slope/query
Divide & Conquer DP Opt.	When opt[i][j] ≤ opt[i][j+1] (quadrangle inequality)
Aliens Trick (Lagrange)	Add penalty for using resource, binary search penalty

7. Debugging DP

Always test with small n, brute-force verification
Check overflow — MOD every operation
Bounds on dp array — off-by-one kills CF submissions
Initialization — dp[0] or base cases? For min/max, INF or -INF?
State space — can you reduce dimension? (e.g., only last row matters)

← Previous

Constructive

Graph Tricks