DP problems — Fibonacci, coin change (count + min), 0 - 1 knapsack

1. Fibonacci — the "hello world" of overlapping subproblems

WHY it's the canonical DP example: Naive recursion recomputes the same values over and over.

                 F(5)
           /            \
        F(4)            F(3)      <- F(3) computed here
       /    \          /    \
    F(3)    F(2)    F(2)   F(1)   <- F(3) AGAIN, F(2) thrice...

The recursion tree has $\approx \phi^n$ nodes (exponential, $\phi=1.618$) but only $n+1$ distinct values. That gap is exactly what memoization kills.

HOW — three increasingly lean versions:

# (a) Top-down memoization
def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
 
# (b) Bottom-up table
def fib(n):
    dp = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
 
# (c) Space-optimized — we only ever need the last two
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

2. Coin Change — two flavors

You have coin denominations coins[] (unlimited supply each — this is unbounded knapsack style) and a target amount.

2a. Count the number of ways to make amount

WHY order matters here. To count combinations (not permutations) we must fix coin order: loop coins on the outside, amount on the inside. This guarantees we never use coin 2 before coin 1 in two different orders and double count.

$\text{dp}[a] \;{+}{=}\; \text{dp}[a - c] \quad \text{for each coin } c$

def count_ways(coins, amount):
    dp = [0]*(amount+1)
    dp[0] = 1                       # one way: empty set
    for c in coins:                 # coins OUTSIDE -> combinations
        for a in range(c, amount+1):
            dp[a] += dp[a-c]
    return dp[amount]

2b. Minimum number of coins to make amount

$\text{dp}[a] \;=\; \min_{c \le a}\big(\text{dp}[a-c] + 1\big), \qquad \text{dp}[0]=0$

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

3. 0/1 Knapsack — each item used at most once

WHY a 2D state. For each item we make a binary choice; the only thing the future cares about is how much capacity remains and which items are still available. So state = (items considered, capacity used).