20. Dynamic Programming — Basics

What you'll learn

• 1Explain the two DP approaches (memoization vs tabulation)
• 2Find the recurrence and the base case
• 3Apply DP to Fibonacci, stairs, coin change

Overview

If a problem has 'optimal substructure' (the answer depends on answers to smaller subproblems) and 'overlapping subproblems' (the same subproblem is asked many times), DP can convert exponential brute force to polynomial.

Core Concepts

1. Top-down (memoization)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

# Or manual:
memo = {}
def fib(n):
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

2. Bottom-up (tabulation)

def fib(n):
    if n < 2: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Space-optimized (only last 2 values needed):
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

3. Comparison

4. Climbing stairs

# Reach step n by taking 1 or 2 steps at a time
def stairs(n):
    if n <= 2: return n
    dp = [0] * (n + 1)
    dp[1] = 1; dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

5. Coin change (minimum coins)

def min_coins(coins, target):
    INF = float('inf')
    dp = [INF] * (target + 1)
    dp[0] = 0
    for amount in range(1, target + 1):
        for c in coins:
            if c <= amount:
                dp[amount] = min(dp[amount], dp[amount - c] + 1)
    return dp[target] if dp[target] != INF else -1

Examples

Example 1 — src/01_fibonacci_memo.py

Fibonacci with lru_cache memoization.

Example 2 — src/02_fibonacci_tab.py

Fibonacci bottom-up + space-optimized.

Example 3 — src/03_climbing_stairs.py

Stairs with cost constraints (BOJ 2579).

Example 4 — src/04_coin_change.py

Coin change minimum coins.

Common Mistakes

1. Recursion depth blow-up with memoization on N=10⁶. Use tabulation.
2. Forgetting base cases — dp[0], dp[1] need explicit initialization.
3. Off-by-one in dp size: `dp = [0] * n` vs `dp = [0] * (n + 1)`.
4. Confusing 'min coins' with 'number of ways to make change' — different recurrences.

Recap

• DP = recurrence + base case + storage.
• Top-down (memoize) for intuitive code; bottom-up (tabulate) for performance.
• Always state the recurrence in plain English before coding.

Try It

1. BOJ 2579 (Climbing stairs).
2. BOJ 1463 (Make 1).
3. BOJ 11726 (2×n tiling).