S033 · Dynamic Programming — Memoisation & Tabulation

"""dp_lab.py — six classic DP problems in one file."""
from __future__ import annotations
import bisect
from functools import lru_cache
from typing import List
 
# ---------- 1. Fibonacci — three implementations ----------
def fib_naive(n: int) -> int:
    """Exponential. fib_naive(35) already stutters."""
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    """Top-down. O(n) time and space."""
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
 
def fib_tab(n: int) -> int:
    """Bottom-up, O(1) space via rolling variables."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
 
# ---------- 2. Climbing stairs — the ‘hello world’ of DP ----------
def climb_stairs(n: int) -> int:
    """Ways to climb n stairs taking 1 or 2 steps at a time. = fib(n+1)."""
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
 
# ---------- 3. Coin change — minimum coins ----------
def coin_change(coins: List[int], amount: int) -> int:
    """Fewest coins summing to `amount`, or -1 if impossible."""
    INF = float("inf")
    dp = [0] + [INF] * amount            # dp[0] = 0; rest start unreachable
    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
 
# ---------- 4. Longest Increasing Subsequence — O(n²) and O(n log n) ----------
def lis_quadratic(nums: List[int]) -> int:
    """dp[i] = LIS ending at i. O(n²) but easy to remember."""
    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)
 
def lis_nlogn(nums: List[int]) -> int:
    """Patience-sort DP with binary search — the interview flex."""
    tails: List[int] = []                # tails[k] = smallest possible tail of an LIS of length k+1
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)              # extend
        else:
            tails[i] = x                 # tighten
    return len(tails)
 
# ---------- 5. Edit (Levenshtein) distance — 2-D DP ----------
def edit_distance(a: str, b: str) -> int:
    """Minimum single-character insert/delete/replace to turn `a` into `b`."""
    m, n = len(a), len(b)
    # dp[i][j] = distance between a[:i] and b[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                     # delete all of a[:i]
    for j in range(n + 1):
        dp[0][j] = j                     # insert all of b[:j]
    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]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],        # delete a[i-1]
                    dp[i][j - 1],        # insert b[j-1]
                    dp[i - 1][j - 1],    # replace
                )
    return dp[m][n]
 
# ---------- 6. 0/1 Knapsack — the OR classic ----------
def knapsack(weights: List[int], values: List[int], capacity: int) -> int:
    """Max value packable into capacity; each item usable at most once."""
    n = len(weights)
    dp = [0] * (capacity + 1)            # rolling 1-D over items
    for i in range(n):
        w, v = weights[i], values[i]
        for c in range(capacity, w - 1, -1):   # iterate BACKWARDS so we don't reuse item i
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]
 
# ---------- Demo ----------
if __name__ == "__main__":
    print("fib_memo(50)         =", fib_memo(50))
    print("fib_tab(100)         =", fib_tab(100))
    print("climb_stairs(10)     =", climb_stairs(10))         # 89
    print("coin_change([1,3,4], 6)          =", coin_change([1, 3, 4], 6))     # 2
    print("coin_change([2], 3)              =", coin_change([2], 3))           # -1
    print("lis_quadratic([10,9,2,5,3,7,101,18]) =", lis_quadratic([10,9,2,5,3,7,101,18]))
    print("lis_nlogn([10,9,2,5,3,7,101,18])     =", lis_nlogn([10,9,2,5,3,7,101,18]))
    print("edit_distance('kitten', 'sitting')   =", edit_distance("kitten", "sitting"))  # 3
    print("knapsack([2,3,4,5], [3,4,5,6], 5)    =", knapsack([2,3,4,5], [3,4,5,6], 5))    # 7