Dynamic Programming — DP and Memoization

After This Topic

You will be able to identify situations where dynamic programming is needed and solve problems using both top-down (memoization) and bottom-up (tabulation) approaches.

Problems with Repeated Calculations

When implementing the Fibonacci sequence recursively:

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

print(fib(35))  # 9227465 — about 4 seconds
print(fib(50))  # ... never finishes

When calculating fib(5), fib(3) is called twice, and fib(2) is called three times. For fib(50), the number of redundant calls reaches billions.

fib(5)
├── fib(4)
│   ├── fib(3)        ← calculated here
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)        ← calculated again
└── fib(3)            ← calculated again
    ├── fib(2)        ← calculated again
    └── fib(1)

Time complexity: O(2^n). This problem can be solved by remembering the answers that have already been calculated.

Conditions for Dynamic Programming

Two things are required to apply DP:

1. Overlapping Subproblems

The same small problem is repeated multiple times, like fib(3) in the Fibonacci sequence.

2. Optimal Substructure

The optimal solution to a larger problem is composed of optimal solutions to smaller problems, like fib(n) = fib(n-1) + fib(n-2).

If both conditions are met, DP can be applied. If not, other methods (greedy, divide and conquer, etc.) should be used.

Top-Down — Memoization

Maintain the recursion from "top to bottom," but store the results of calculations in a dictionary (or array):

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

print(fib(50))   # 12586269025 — completes immediately
print(fib(100))  # 354224848179261915075

fib(50) changes from 4 seconds to immediate. Each fib(k) is calculated only once, so the time complexity is O(n).

In Python, you can use functools.lru_cache to write it more cleanly:

from functools import lru_cache

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

Memoization is completed with a single line of decorator.

Bottom-Up — Tabulation

Solve problems from "bottom to top," starting with smaller problems:

def fib(n):
    if n <= 1:
        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]

Since no recursion is used, there is no risk of stack overflow. fib(10000) is also not a problem.

Space optimization: For Fibonacci, only the two most recent values are needed:

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

O(n) time, O(1) space.

Top-Down vs. Bottom-Up

In general, bottom-up is slightly faster (no function call overhead) and space optimization is easier. However, there are cases where converting the recurrence relation to a loop is not intuitive, so choose based on the situation.

Representative Problem: Climbing Stairs

There are n stairs, and you can climb 1 or 2 stairs at a time. How many ways are there to reach the top?

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1  # 1 step: 1 way
    dp[2] = 2  # 2 steps: 1+1 or 2, 2 ways
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_stairs(5))   # 8
print(climb_stairs(10))  # 89

To reach the i-th step, you can either climb 1 step from (i-1) or 2 steps from (i-2). dp[i] = dp[i-1] + dp[i-2] — the same structure as Fibonacci.

Representative Problem: 0-1 Knapsack

A knapsack with capacity W, and n items. Each item can either be included or excluded (0-1). Maximize the total value:

def knapsack(W, items):
    n = len(items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]  # Not included
            if w >= weight:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)

    return dp[n][W]

items = [(2, 3), (3, 4), (4, 5), (5, 6)]  # (weight, value)
print(knapsack(8, items))  # 10

dp[i][w] is the maximum value that can be achieved using the first i items with a capacity of w. For each item, record the maximum of the two options: "include" vs. "exclude."

DP Problem Solving Pattern

1. State Definition: Clearly define what dp[i] represents.
2. Recurrence Relation: Express dp[i] in terms of previous states.
3. Base Case: Fill in the answers for the smallest problems.
4. Order: Determine the order in which to fill the table.
5. Result Extraction: Obtain the answer from dp[n] or max(dp).

In coding tests, a large number of problems that ask for "number of ways," "minimum/maximum," or "whether it is possible" are DP problems. If the input size is in the hundreds to thousands, suspect O(n²) DP.

Distinguishing DP from Non-DP Problems

Both DP and greedy algorithms utilize "optimal substructure," but greedy algorithms go in one direction without backtracking, while DP records the results of all possible choices in a table.

Key Takeaway: Dynamic programming is a strategy of "not repeating the same calculations." It is implemented in two ways: memoization (top-down, recursion + cache) and tabulation (bottom-up, loop + table), and it reduces O(2^n) to O(n) or O(n²).