Algorithms · Lesson 6 of 6

Dynamic Programming

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

• Advanced
• 20 min read
• 3 objectives

Before this lessonLesson 5: Backtracking

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).

Do not solve the same problem twice

If a friend asks you the same difficult question ten times, you would write the answer down after the first time. Dynamic programming (DP) applies that idea to algorithms. When a problem breaks into smaller subproblems that repeat, you solve each subproblem once, store the result, and reuse it. Problems that took exponential time recursively often become fast and polynomial.

Two signs that DP may help: the problem asks for a best/count/yes-no answer, and a naive recursion keeps recomputing the same inputs.

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).

From slow recursion to DP, in three steps

Count ways to climb n stairs taking 1 or 2 steps at a time. First the plain recursion, then the same idea with a memo, then a bottom-up table.

from functools import lru_cache

def ways_slow(n):
    return 1 if n <= 1 else ways_slow(n - 1) + ways_slow(n - 2)

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

def ways_table(n):
    dp = [1, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(ways_slow(15), ways_memo(15), ways_table(15))
print(ways_table(50))

987 987 987
20365011074

The DP recipe

• State: what does dp[i] mean, in one sentence?
• Transition: how does dp[i] follow from smaller states?
• Base cases: which values are known directly?
• Order: fill the table so dependencies are ready first.
• Answer: which cell holds the result?

Coin change, where greedy failed

DP solves the coin problem that greedy got wrong. dp[a] is the fewest coins needed to make amount a.

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

print(fewest_coins([1, 3, 4], 6))      # 2  (3 + 3)
print(fewest_coins([2], 3))            # -1 (impossible)

2
-1

For 6 with coins 1, 3, 4 greedy needed three coins; DP correctly finds two. DP considers every option for each amount, remembering the best.

Key takeaways

• DP stores answers to overlapping subproblems so each is solved once.
• Define the state, the transition and the base cases, then fill a table (or memoize).
• DP finds optimal answers where greedy can fail, at the cost of extra memory.

# Write your solution here