Dynamic programming: memoisation to tabulation

Recognise overlapping subproblems, write the recurrence, then choose top-down memoisation or a bottom-up table with reduced space.

Recognising a DP problem

A problem is a DP problem when it asks for an optimum or a count, and when the same subproblem appears in more than one place. If the subproblems never repeat, memoisation buys nothing and the answer is plain recursion or divide and conquer.

from functools import lru_cache

# Step 1: write the brute-force recursion, however slow
def fib_naive(n: int) -> int:
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)     # O(2^n): the same n many times

# Step 2: memoise it. One decorator, no restructuring.
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)       # O(n) time, O(n) space

# Step 3: tabulate it. The order is explicit and recursion is gone.
def fib_tab(n: int) -> int:
    if n < 2:
        return n
    prev, cur = 0, 1
    for _ in range(2, n + 1):
        prev, cur = cur, prev + cur                # O(1) space
    return cur

# The DP checklist, in order:
#   1. What is the state? Name it in words. "The best answer for the first i items
#      with capacity c" is a state; "the answer" is not.
#   2. What is the recurrence? Each state from strictly smaller states.
#   3. What are the base cases?
#   4. In what order can the table be filled, so every dependency exists?
#   5. Can the state be reduced? Often one row or a few variables suffice.

def stairs(n: int) -> int:
    """Count the ways to climb when 1 or 2 steps are allowed at a time."""
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b


if __name__ == "__main__":
    print(fib_naive(20), fib_memo(200), fib_tab(200))
    print(stairs(5))       # 8

• lru_cache on a method keeps self in the key, which holds the instance alive. Use an explicit cache or a module-level function.
• Python's default recursion limit applies to memoised recursion as well. A DP with a depth of 10,000 needs sys.setrecursionlimit plus a configured thread stack, or the tabulated form.
• Memoisation computes only the states that are reachable; tabulation computes every state. When most states are unreachable, top-down is faster.
• Tabulation has no function-call overhead and is easier to reduce in space. When every state is needed, it is the better choice.

Tabulation and space reduction

from typing import Sequence

def longest_increasing_subsequence(nums: Sequence[int]) -> int:
    """O(n squared) DP: best[i] is the longest run ending exactly at i."""
    if not nums:
        return 0
    best = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                best[i] = max(best[i], best[j] + 1)
    return max(best)


def lis_binary_search(nums: Sequence[int]) -> int:
    """O(n log n): maintain the smallest possible tail for each length."""
    import bisect
    tails: list[int] = []
    for x in nums:
        i = bisect.bisect_left(tails, x)     # strictly increasing
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)                        # NOTE: tails is not the subsequence itself


def house_robber(nums: Sequence[int]) -> int:
    """Two variables replace the whole table: the classic space reduction."""
    prev = cur = 0
    for x in nums:
        prev, cur = cur, max(cur, prev + x)
    return cur


def edit_distance(a: str, b: str) -> int:
    """2D table; the recurrence needs only the previous row, so space is O(min)."""
    if len(a) < len(b):                      # keep the shorter string as the row
        a, b = b, a
    previous = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        current = [i] + [0] * len(b)
        for j, cb in enumerate(b, 1):
            cost = 0 if ca == cb else 1
            current[j] = min(
                previous[j] + 1,                         # delete
                current[j - 1] + 1,                      # insert
                previous[j - 1] + cost,                  # substitute or match
            )
        previous = current
    return previous[-1]


def coin_change_ways(coins: Sequence[int], amount: int) -> int:
    """Count combinations, not permutations: iterate coins on the OUTER loop."""
    ways = [0] * (amount + 1)
    ways[0] = 1
    for c in coins:
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]


if __name__ == "__main__":
    print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]))   # 4
    print(lis_binary_search([10, 9, 2, 5, 3, 7, 101, 18]))                # 4
    print(house_robber([2, 7, 9, 3, 1]))                                  # 12
    print(edit_distance("kitten", "sitting"))                             # 3
    print(coin_change_ways([1, 2, 5], 5))                                 # 4

Common DP mistakes

from functools import lru_cache
from typing import Sequence

# MISTAKE 1: the state does not carry enough information.
# "best[i] = the best answer for the first i items" is not enough when the
# remaining capacity matters. Add it: best[i][c].

# MISTAKE 2: a state that is not acyclic. If state A depends on state B and
# B depends on A, the recursion never terminates. Order the dependency.

# MISTAKE 3: memoising something that is not pure.
@lru_cache(maxsize=None)
def bad(i: int) -> int:
    return next(counter) + i        # a cache hit returns a stale value

# MISTAKE 4: forgetting the base case for the empty input.
def subset_sum(nums: Sequence[int], target: int) -> bool:
    """Space-reduced 0/1 knapsack. The inner loop must run DOWNWARD."""
    reachable = [False] * (target + 1)
    reachable[0] = True
    for x in nums:
        for c in range(target, x - 1, -1):     # descending: each item used once
            if reachable[c - x]:
                reachable[c] = True
    return reachable[target]


def subset_sum_unbounded(nums: Sequence[int], target: int) -> bool:
    """The same problem with unlimited copies: the loop runs UPWARD."""
    reachable = [False] * (target + 1)
    reachable[0] = True
    for x in nums:
        for c in range(x, target + 1):         # ascending: unlimited reuse
            if reachable[c - x]:
                reachable[c] = True
    return reachable[target]


counter = iter(range(10 ** 6))


def knapsack_01(weights: Sequence[int], values: Sequence[int], capacity: int) -> int:
    """The canonical space-reduced 0/1 knapsack."""
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # descending
            best[c] = max(best[c], best[c - w] + v)
    return best[capacity]


if __name__ == "__main__":
    print(subset_sum([3, 34, 4, 12, 5, 2], 9))            # True
    print(knapsack_01([1, 3, 4, 5], [1, 4, 5, 7], 7))     # 9

The direction of the inner loop in a 1D knapsack is not a style choice: descending keeps each item used at most once, ascending allows unlimited reuse. If your subset-sum answer allows the same element twice, this is the line to check first.

FAQ

Related

Dynamic programming patterns: knapsack, edit distance, LCS Recursion, backtracking and divide and conquer

Last refreshed 2026-09-18.