Dynamic programming for beginners

When DP applies

• Overlapping subproblems: the same smaller problem is solved again and again.
• Optimal substructure: the best answer is built from the best answers to smaller problems.

Step 1: plain recursion

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(5) calls fib(3) twice and fib(2) three times. The work grows exponentially, roughly O(2^n).

Step 2: memoization (top-down)

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

print(fib(50))   # 12586269025

Each value is computed once, so the time drops to O(n). In Python you can also use functools.lru_cache.

Step 3: tabulation (bottom-up)

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

Fill a table from the smallest case upward. No recursion, so no recursion limit.

A real example: climbing stairs

You can climb 1 or 2 steps at a time. How many ways reach step n? To land on step n you came from n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2).

def climb(n):
    a, b = 1, 1          # ways to reach step 0 and step 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print(climb(4))   # 5

A recipe for any DP problem

1. Define the state: what does dp[i] mean in words?
2. Write the recurrence: how does dp[i] use smaller states?
3. Set the base cases.
4. Choose the order to fill the table.
5. Read off the answer, then reduce memory if only the last few values are needed.

• From recursion to memoization to a table
• Recursion explained
• Data structures and algorithms course
• Competitive programming course