Dynamic Programming

Dynamic programming is a name that intimidates, but the idea under it is plain: if you are going to solve the same subproblem more than once, solve it once and remember the answer.

For that to help, two things must both be true. There must be overlapping subproblems — the recursion keeps revisiting the same smaller inputs (naive Fibonacci computes fib(3) over and over). And there must be optimal substructure — the best answer to the whole is built from best answers to its parts (the shortest path from A to C through B is the shortest A-to-B path plus the shortest B-to-C path). When both hold, you have a choice of two equivalent styles.

Two directions: memoize or tabulate

Memoization keeps the natural recursion and just caches results — top-down. You write the algorithm the obvious way and check the cache before doing real work:

from functools import lru_cache

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

The cache turns the call tree from O(2ⁿ) into O(n): each fib(k) is computed once and read thereafter. Tabulation flips the direction — bottom-up. You fill a table from the smallest subproblems forward, with no recursion at all:

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

Same O(n), but no call stack to overflow, and often you can shrink the table — here, keeping only the last two values makes it O(1) space. Memoization is easiest when you already have the recursion and only some subproblems matter; tabulation wins when inputs are huge or you need the whole table to reconstruct the answer.

The shape of every DP: a recurrence

Every DP problem hides a recurrence. The 0/1 knapsack — fit the most value into a bag of capacity W, each item taken or not — is dp[i][w] = max(skip item i, take item i). Find that one line and the rest is bookkeeping. Let us see it in full on a problem you use every day.

Edit distance, the full picture

Edit distance is the fewest single-character insertions, deletions, and substitutions to turn one word into another. Lay the two words on the axes of a grid; cell dp[i][j] is the cost to convert the first i letters of one into the first j of the other. If the current letters match, the cost is whatever the diagonal already held — free. If they differ, it is one plus the cheapest of three neighbours: diagonal (substitute), up (delete), left (insert).

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i        # delete i chars to reach ""
    for j in range(n + 1): dp[0][j] = j        # insert j chars from ""
    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]                 # match — free
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],        # substitute
                                   dp[i - 1][j],            # delete
                                   dp[i][j - 1])            # insert
    return dp[m][n]

for a, b in [("cat", "car"), ("kitten", "sitting"), ("sunday", "saturday")]:
    print(f"{a} -> {b}: {edit_distance(a, b)}")

cat -> car: 1
kitten -> sitting: 3
sunday -> saturday: 3

Filling the table is O(m·n), and once it is full, tracing the chosen neighbours back from the corner reconstructs the actual edits.

Practice