Dynamic Programming

What DP is — and isn't

Dynamic programming is the technique of solving a problem by breaking it into overlapping subproblems and CACHING the answer to each subproblem so you only solve it once. It applies when two conditions hold:

• Optimal substructure — the optimal answer can be composed from optimal answers to subproblems.
• Overlapping subproblems — the SAME subproblems appear many times in the recursion.

DP is not a single algorithm — it's a way of thinking. The hardest part is identifying the STATE: what variables uniquely describe a subproblem? Once you have that, the recurrence usually falls out.

Two flavors: memoization vs tabulation

• Memoization (top-down) — write the natural recursion, then cache results in a dict. Easy to write; uses recursion stack.
• Tabulation (bottom-up) — fill a table from base cases up to the answer, with explicit loops. Often more memory-efficient.

Example 1: Fibonacci (the canonical bad recursion)

# Naive — O(2^n). For n=40 it already takes seconds.
def fib_slow(n):
    if n < 2: return n
    return fib_slow(n - 1) + fib_slow(n - 2)

# Top-down with @cache — O(n)
from functools import cache

@cache
def fib_memo(n):
    if n < 2: return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# Bottom-up — O(n) time, O(1) space
def fib_tab(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_tab(50))    # instant

Example 2: Climbing stairs

You can climb 1 or 2 stairs at a time. How many ways to climb n stairs? Define `ways(n) = ways(n-1) + ways(n-2)` — and it's just Fibonacci in disguise.

Example 3: Coin change (a classic 1D DP)

Given coin denominations and an amount, find the minimum number of coins to make that amount. State: `dp[i]` = min coins to make amount i. Recurrence: try every coin.

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 2, 5], 11))   # 3 (5 + 5 + 1)

Example 4: 2D DP — longest common subsequence

Given two strings, find the length of the longest sequence of characters appearing in BOTH (not necessarily contiguous). State: `dp[i][j]` = LCS length of first i chars of A and first j chars of B.

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]

print(lcs("ABCBDAB", "BDCAB"))   # 4

How to spot a DP problem

• Asking for the MINIMUM, MAXIMUM, COUNT, or BOOLEAN of something over many choices.
• You can describe \"the answer for input X\" in terms of \"the answer for slightly smaller inputs\".
• A naive recursion would have exponential time because of repeated subproblems.