Dynamic programming — patterns and classic problems

DP is “remembered recursion.” Identify subproblems, compute each once, reuse via memoization (top-down) or tabulation (bottom-up).

When to recognize DP

The problem asks for an optimum (max, min, count) over choices
Solving for n decomposes into smaller subproblems with overlap
Greedy doesn’t quite work — local choices interact

The 5-step approach:

Define the state — what does dp[i] (or dp[i][j]) mean?
Find the recurrence — how does dp[i] relate to smaller subproblems?
Identify base cases — what’s dp[0], dp[1]?
Decide order — top-down recursion + memo, or bottom-up loop?
Optimize space if you only need recent rows.

Pattern: 1D — Fibonacci / climbing stairs

def climb_stairs(n):
    """Steps of 1 or 2; how many ways to climb n stairs?"""
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(n - 2):
        a, b = b, a + b
    return b

State: dp[i] = ways to reach step i. Recurrence: dp[i] = dp[i-1] + dp[i-2]. Space-optimized to two variables.

Pattern: 1D — house robber

def rob(nums):
    """Max sum of non-adjacent elements."""
    prev_no, prev_yes = 0, 0
    for x in nums:
        prev_no, prev_yes = max(prev_no, prev_yes), prev_no + x
    return max(prev_no, prev_yes)

State: at each index, track best sum if we don’t take this house vs if we do. Two variables suffice.

Pattern: longest increasing subsequence

def length_of_lis(nums):
    """O(n²) version."""
    if not nums: return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

State: dp[i] = length of longest increasing subseq ending at i. Recurrence: extend any earlier subseq with nums[j] < nums[i].

O(n log n) version using binary search:

import bisect

def length_of_lis_fast(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

tails[k] = smallest tail of any increasing subseq of length k+1. Replace-or-append maintains the invariant. The length of tails is the answer.

Pattern: 2D — longest common subsequence

def lcs(a: str, b: str) -> int:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

State: dp[i][j] = LCS of a[:i] and b[:j]. O(nm) time and space; can reduce to O(min(n,m)) space using only two rows.

Pattern: 0/1 knapsack

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]   # don't take item i
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

State: dp[i][w] = best value using first i items with total weight ≤ w. Each item: take or skip.

Space optimization: process items right-to-left in a 1D array:

def knapsack_1d(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w_i, v_i in zip(weights, values):
        for w in range(capacity, w_i - 1, -1):    # right-to-left
            dp[w] = max(dp[w], dp[w - w_i] + v_i)
    return dp[capacity]

Reverse iteration prevents using the same item twice.

Pattern: coin change (unbounded knapsack variant)

def coin_change(coins, amount):
    """Min coins to make amount, or -1 if impossible."""
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Bottom-up. State: dp[a] = min coins for amount a. Each coin can be used any number of times (use forward iteration over amounts).

Memoization template (top-down)

from functools import lru_cache

def solve_recursive(n):
    @lru_cache(maxsize=None)
    def f(state):
        if base_case(state):
            return base_value
        return min(f(next_state) + cost for next_state in transitions(state))
    return f(n)

Use top-down when:

Subproblem space is sparse (don’t want to fill a full table)
Recurrence is natural to express recursively
You want to skip unreachable states

Use bottom-up when:

Need to reason about order
Want explicit space optimization
Avoid recursion stack overhead

Common mistakes

State that doesn’t capture enough — if dp[i] depends on something other than i and computed values, your state is incomplete.
Infinite recursion — base case missing or recurrence reaches outside the defined domain.
Space waste — many DPs only need the last 1-2 rows. Always ask if you can shrink.
Off-by-one — state index i meaning “first i items” vs “item at index i” — pick one and stick with it.
Using a dict instead of a list when keys are 0..n — list is faster.

Interview angle

The DP question almost always has the form: “Given this constraint problem, find max/min/count of something.” Your job is to extract the state, write the recurrence, and convert to code.

Practice translating from a recursive solution (clear but exponential) → memoized (correct, polynomial) → tabulated (often more efficient) → space-optimized.