dp-patterns

What this skill does

# Dynamic Programming Patterns

This reference covers eight foundational dynamic programming patterns commonly encountered in algorithmic problem solving. Each pattern includes recognition signals to identify when a problem maps to the technique, a working Python template, and specific edge cases and mistakes to watch for. Load this skill when solving optimization, counting, or subsequence problems that exhibit optimal substructure and overlapping subproblems.

## General DP Approach

Before selecting a specific pattern, apply this checklist:

1. **Identify the state**: What information do you need to uniquely describe a subproblem? (index, remaining capacity, bitmask of visited nodes)
2. **Define the recurrence**: How does the answer for the current state relate to answers for smaller states?
3. **Establish base cases**: What are the trivial subproblems with known answers?
4. **Determine iteration order**: Ensure every state is computed before it is needed (bottom-up) or use memoization (top-down)
5. **Optimize space**: If dp[i] depends only on dp[i-1] (or a small window), use rolling arrays instead of the full table

## Pattern Recognition Table

| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| "count the number of ways", "how many distinct paths" | Fibonacci / Climbing Stairs | O(N) time, O(1) space |
| "maximize value with weight limit", "partition into two equal subsets" | 0/1 Knapsack | O(N * W) time, O(W) space |
| "longest common subsequence", "minimum edit operations" | LCS / Edit Distance | O(N * M) time, O(min(N, M)) space |
| "longest increasing subsequence", "minimum number of envelopes" | LIS | O(N log N) time, O(N) space |
| "unique paths in grid", "minimum cost to reach bottom-right" | Grid DP | O(R * C) time, O(C) space |
| "maximum subarray sum", "best contiguous segment" | Kadane's Algorithm | O(N) time, O(1) space |
| "fewest coins to make amount", "ways to combine denominations" | Coin Change / Unbounded Knapsack | O(N * amount) time, O(amount) space |
| "visit all nodes exactly once", "assign N items optimally", N <= 20 | Bitmask DP | O(2^N * N) time, O(2^N) space |

## Constraint-to-Technique Mapping

Use input constraints to narrow the viable DP approach:

| Constraint Range | Viable Approaches |
|---|---|
| N <= 20 | Bitmask DP, brute-force with memoization |
| N <= 500 | O(N^3) DP (interval DP, Floyd-Warshall) |
| N <= 5,000 | O(N^2) DP (LIS quadratic, 2D tables) |
| N <= 100,000 | O(N log N) DP (LIS with binary search, segment tree optimization) |
| N <= 1,000,000 | O(N) DP (Fibonacci-style, Kadane, sliding window) |
| N * W <= 10^7 | Knapsack variants (0/1 or unbounded) |
| Grid R * C <= 10^6 | Standard grid DP with rolling array |

### Fibonacci / Climbing Stairs

**Recognition Signals**
- "How many ways to reach step N"
- "Count distinct ways to combine steps of size 1, 2, ..."
- "Decode ways" (how many ways to decode a digit string into letters)
- Recurrence follows f(n) = f(n-1) + f(n-2) or a generalized k-step variant

**Core Idea**
The answer at position N depends only on a fixed number of prior positions. Build the result iteratively from the base cases, keeping only the last k values in memory. This generalizes beyond two-step Fibonacci to any linear recurrence. When the recurrence has a fixed number of terms, space reduces to O(k) where k is the number of terms. For very large N (e.g., N > 10^18), matrix exponentiation can compute the result in O(k^3 log N).

**Python Template**
```python
def climb_stairs(n: int, steps: list[int] | None = None) -> int:
    """Count ways to reach step n using allowed step sizes."""
    if steps is None:
        steps = [1, 2]
    max_step = max(steps)
    # dp[i] = number of ways to reach step i
    dp: list[int] = [0] * (max_step + 1)
    dp[0] = 1  # base case: one way to stay at ground
    for i in range(1, n + 1):
        total = 0
        for s in steps:
            if i - s >= 0:
                total += dp[(i - s) % (max_step + 1)]
        dp[i % (max_step + 1)] = total
    return dp[n % (max_step + 1)]
```

**Key Edge Cases**
- n = 0: exactly 1 way (do nothing)
- n = 1 with only step size 2: 0 ways (unreachable)
- Large n with modular arithmetic required (typically mod 10^9 + 7)
- Negative step sizes are not valid; guard input

**Common Mistakes**
- Forgetting the base case dp[0] = 1 and getting all zeros
- Off-by-one in the loop range (should go up to n inclusive)
- Not applying modular arithmetic early, causing integer overflow in languages with fixed-width integers

### 0/1 Knapsack

**Recognition Signals**
- "Maximize total value without exceeding capacity W"
- "Can you partition the array into two subsets with equal sum"
- "Select a subset such that the sum equals target"
- Each item can be used at most once

**Core Idea**
For each item, decide to include or exclude it. Build a 1D DP array where dp[w] indicates the best achievable value (or a boolean for subset sum) using capacity w. Iterate items in the outer loop and capacity in reverse to ensure each item is used at most once. Common variants include subset sum (boolean dp), partition equal subset sum (check if total/2 is achievable), and target sum with +/- signs (offset the DP index by a constant).

**Python Template**
```python
def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
    """Return maximum value achievable within capacity."""
    n = len(weights)
    dp: list[int] = [0] * (capacity + 1)
    for i in range(n):
        # Traverse capacity in reverse to avoid reusing item i
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]
```

**Key Edge Cases**
- All items heavier than capacity: answer is 0
- Capacity is 0: answer is 0 regardless of items
- Single item that exactly matches capacity
- Subset sum variant: dp is boolean, dp[0] = True

**Common Mistakes**
- Iterating capacity forward instead of reverse, which allows items to be picked multiple times (that is unbounded knapsack)
- Confusing 0/1 knapsack with unbounded knapsack when items are reusable
- Not handling the case where weights[i] > capacity (skip the inner loop for that item)

### Longest Common Subsequence (LCS)

**Recognition Signals**
- "Find the longest common subsequence of two strings"
- "Minimum number of insertions and deletions to transform A into B"
- "Edit distance between two strings"
- Two sequences compared element by element

**Core Idea**
Build a 2D table where dp[i][j] represents the LCS length of the first i characters of A and first j characters of B. If characters match, extend the diagonal; otherwise take the max of skipping from either side. Edit distance uses the same table structure with insertion, deletion, and substitution costs, where each operation adds 1 (or a weighted cost) and the goal switches from maximizing to minimizing. The "minimum deletions to make two strings equal" variant is directly: len(A) + len(B) - 2 * LCS(A, B).

**Python Template**
```python
def lcs(a: str, b: str) -> int:
    """Return length of the longest common subsequence."""
    m, n = len(a), len(b)
    # Use two rows to reduce space from O(m*n) to O(min(m,n))
    if m < n:
        a, b, m, n = b, a, n, m
    prev: list[int] = [0] * (n + 1)
    curr: list[int] = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)
    return prev[n]
```

**Key Edge Cases**
- One or both strings empty: LCS is 0
- Strings are identical: LCS equals the full length
- No common characters at all: LCS is 0
- Very long strings (space optimization with rolling rows is critical)

**Common Mistakes**
- Mixing up 0-indexed and 1-indexed access between the string and the DP table
- Forgetting to reset the curr row between it