Dynamic Programming for Beginners: Memoization and Tabulation

Dynamic programming (DP) solves a problem by breaking it into smaller subproblems, solving each subproblem once, and storing the answers so they can be reused. It turns many exponential-time recursive solutions into polynomial time.

DP applies when a problem has two properties:

1. Overlapping subproblems: the same smaller problems come up again and again.
2. Optimal substructure: the best answer to the whole problem is built from best answers to subproblems.

The problem DP fixes#

How many ways can you climb n stairs, taking 1 or 2 steps at a time? To reach step n, your last move came from step n − 1 or n − 2, so ways(n) = ways(n − 1) + ways(n − 2). Written directly, the recursion repeats work just like naive Fibonacci:

calls = 0

def ways(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

for n in [10, 20, 30]:
    calls = 0
    print(n, ways(n), "calls:", calls)

10 89 calls: 177
20 10946 calls: 21891
30 1346269 calls: 2692537

The number of calls grows exponentially, even though there are only n different subproblems.

Top-down: memoization#

Keep the recursion, but store each answer the first time it is computed:

def ways(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = ways(n - 1, memo) + ways(n - 2, memo)
    return memo[n]

print(ways(30), ways(90))

1346269 4660046610375530309

Each subproblem is solved once: O(n) time and O(n) space. functools.lru_cache (or cache) does the same with a decorator.

Bottom-up: tabulation#

Instead of recursing from n downwards, fill a table from the smallest subproblems upwards. No recursion, so no recursion limit:

def ways(n):
    table = [0] * (n + 1)
    table[0] = 1
    if n >= 1:
        table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

print([ways(n) for n in range(10)])
print(ways(1000) % 1_000_000_007)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
107579939

Space optimisation#

Each entry only needs the previous two, so two variables replace the table: O(1) space.

def ways(n):
    prev2, prev1 = 1, 1          # ways(0), ways(1)
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

print(ways(10), ways(50))

89 20365011074

Memoization or tabulation?#

Both have the same time complexity. A common workflow is: write the recursion, add memoization, then convert to tabulation if needed.

A five-step method#

For any DP problem:

1. Define the state: what does dp[i] (or dp[i][j]) mean, in words?
2. Write the recurrence: how is dp[i] built from smaller states?
3. Set the base cases: the smallest states, answered directly.
4. Choose the order: fill states so everything needed is already computed.
5. Read the answer: which state holds the final result?

For stair climbing: (1) dp[i] = ways to reach step i; (2) dp[i] = dp[i-1] + dp[i-2]; (3) dp[0] = dp[1] = 1; (4) increasing i; (5) dp[n].

Common mistakes#

Practice#

def ways(n, broken=None):
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        if i == broken:
            continue                    # dp[i] stays 0
        dp[i] = sum(dp[i - k] for k in (1, 2, 3) if i - k >= 0)
    return dp[n]

print(ways(4))
print(ways(4, broken=2))
print(ways(10, broken=5))

7
3
105

Key takeaway#

Next: practise the method on classic problems, in 1D Dynamic Programming.