Dynamic Programming

Overlapping subproblems, memoization, tabulation, knapsack and edit distance.

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems, solving each only once and reusing the stored answer. It turns many exponential recursions into polynomial ones. Two properties signal DP: optimal substructure (the best answer is built from best answers to smaller pieces) and overlapping subproblems (the same small problem comes up repeatedly).

A recipe

• Define the state: what do the parameters of a subproblem mean?
• Write the recurrence: how does a state depend on smaller states?
• Identify the base cases.
• Choose memoization (top-down recursion plus a cache) or tabulation (bottom-up loops filling a table).

Climbing stairs

You can climb 1 or 2 steps at a time. How many ways to reach step n? Ways(n) = ways(n-1) + ways(n-2), since your last move was either 1 or 2 steps.

from functools import lru_cache

@lru_cache(None)
def ways(n):                 # top-down
    return 1 if n <= 1 else ways(n - 1) + ways(n - 2)

def ways_table(n):           # bottom-up, O(1) space
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print(ways(10), ways_table(10))

89 89

Coin change (fewest coins)

State: dp[x] is the fewest coins to make amount x. Recurrence: dp[x] = 1 + min(dp[x - c]) over coins c. This solves the case where greedy failed.

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([4, 3, 1], 6), coin_change([2], 3))

2 -1

0/1 Knapsack

Choose items, each with a weight and value, to maximize value within a capacity. State: dp[w] is the best value with capacity w. Iterate capacity downward so each item is used at most once.

def knapsack(items, capacity):
    dp = [0] * (capacity + 1)
    for weight, value in items:
        for w in range(capacity, weight - 1, -1):
            dp[w] = max(dp[w], dp[w - weight] + value)
    return dp[capacity]

print(knapsack([(1, 1), (3, 4), (4, 5), (5, 7)], 7))

9

Longest common subsequence and edit distance

Two-string problems use a 2D table. dp[i][j] describes the first i characters of one string and the first j of the other. Edit distance (the minimum insert, delete and replace operations to turn one word into another) powers spell checkers.

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
    for j in range(n + 1): dp[0][j] = 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], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

print(edit_distance("kitten", "sitting"))

3

Tips

• Start with plain recursion, then add a cache: the fastest path to a correct DP.
• Draw the table by hand for a tiny input to find the recurrence.
• Look at which earlier cells a cell needs; often you can keep just one or two rows to save memory.
• Time is roughly (number of states) times (work per state).

def lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))   # 4