Dynamic programming

Dynamic programming#

DP is memoization plus a sub-problem decomposition. Two styles, top-down (recursion + cache) and bottom-up (build the table iteratively).

Top-down (memo + recursion)#

from functools import cache

@cache
def lcs(a, b):
    if not a or not b:
        return 0
    if a[-1] == b[-1]:
        return lcs(a[:-1], b[:-1]) + 1
    return max(lcs(a[:-1], b), lcs(a, b[:-1]))

Bottom-up (tabulation)#

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (
                dp[i-1][j-1] + 1
                if a[i-1] == b[j-1]
                else max(dp[i-1][j], dp[i][j-1])
            )
    return dp[m][n]

Top-down is easier to write; bottom-up is faster and avoids recursion-depth limits.

Classic DP problems#

Problem

Sub-problem

Longest common subsequence

lcs(a[:i], b[:j])

Edit distance (Levenshtein)

ed(a[:i], b[:j])

0/1 knapsack

best(items[:i], capacity)

Coin change

min_coins(amount)

Subset sum

can_make(xs[:i], target)

Matrix chain order

best(i, j) over chain [i..j]

References#

Contents