Lesson 35 / 42

Dynamic Programming

Solve overlapping subproblems once, store the answers, and build up.

Two conditions

DP applies when a problem has (1) optimal substructure — the best answer is built from best answers to subproblems — and (2) overlapping subproblems — the same subproblem recurs. Cache each subproblem's answer so you compute it once.

Top-down: memoisation

Write the recursion, then add a cache. Fibonacci goes from O(2^n) to O(n).

from functools import lru_cache

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

Bottom-up: tabulation

Fill a table from base cases upward. Often you can keep only the last row or two — dropping space to O(1).

def climb_stairs(n):     # ways to climb, 1 or 2 steps
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Output:

climb_stairs(5) -> 8

How to approach a DP

  1. Define the state (what do the indices mean?). 2) Write the transition (how does a state depend on smaller states?). 3) Set base cases. 4) Decide order of evaluation. Classics: knapsack, LCS, edit distance, coin change, LIS.