Complexity

Analyzing a DP is usually mechanical: count the states, count the work per state, and multiply. This chapter applies that rule to the classic problems, explains why knapsack is called pseudo-polynomial, compares memoization with tabulation, and shows how to cut memory with rolling arrays.

The basic rule

• Time = number of states x work per transition.
• Space = number of states kept in memory at the same time.

For Fibonacci there are n + 1 states and each does constant work, so time is O(n). For LCS there are (n + 1)(m + 1) states, each doing constant work, so time is O(nm). For coin change with k coin types, each of the amount + 1 states looks at k coins, giving O(amount x k).

Classic problems at a glance

There is rarely a separate best or worst case for a DP: the table is filled completely regardless of the input values. Memoization can be faster in practice when only a fraction of the states is reachable from the starting state.

Pseudo-polynomial time

O(n x W) for knapsack looks polynomial, but W is a number, not the length of the input. Writing W takes only about log2(W) bits, so adding one more bit to the input can double the running time. Such algorithms are called pseudo-polynomial. The 0/1 knapsack problem is NP-hard in general; DP is practical only when capacities are reasonably small integers. When W is huge but n is tiny (say 40 items), meet-in-the-middle enumeration is often a better choice.

Memoization vs tabulation

In Python the recursion limit is the most common surprise. A memoized function on a chain of a few thousand states raises RecursionError, and sys.setrecursionlimit does not always help: recent Python versions also limit how deep calls may nest through C code, and the functools.cache wrapper is written in C. A simple workaround is to warm the cache from small to large, so every call finds its smaller states already stored.

from functools import cache


@cache
def ways(n: int) -> int:
    """Number of ways to climb n stairs with steps of 1 or 2."""
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)


try:
    ways(5_000)
except RecursionError:
    print("too deep")

for i in range(5_001):  # warm up: each call recurses only one level
    ways(i)
print(ways(5_000) % 1_000_000_007)
print(ways.cache_info().currsize)  # 5001 states stored

Warming up is really bottom-up evaluation in disguise. For tens of thousands of states, write the loop directly.

Rolling arrays

If a row of the table depends only on the previous row, you never need more than two rows at once. LCS length in O(min(n, m)) space:

def lcs_length(a: str, b: str) -> int:
    if len(b) > len(a):
        a, b = b, a  # make b the shorter string
    prev = [0] * (len(b) + 1)
    for ch in a:
        cur = [0] * (len(b) + 1)
        for j, bj in enumerate(b, start=1):
            cur[j] = prev[j - 1] + 1 if ch == bj else max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]


print(lcs_length("ABCBDAB", "BDCABA"))  # 4

The trade-off: with only two rows left, you can no longer walk the table backwards to reconstruct the subsequence. Hirschberg's algorithm recovers it in linear space with a divide-and-conquer trick, at roughly twice the time.

Beating the obvious recurrence

Sometimes a better state definition changes the complexity class. The simple LIS recurrence checks every earlier index, giving O(n^2). Keeping, for each length, the smallest possible tail value lets binary search replace the inner loop:

from bisect import bisect_left


def lis_length(nums: list[int]) -> int:
    tails: list[int] = []  # tails[k] = smallest tail of an increasing run of length k + 1
    for x in nums:
        k = bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
        else:
            tails[k] = x
    return len(tails)


print(lis_length([3, 1, 4, 1, 5, 9, 2, 6]))  # 4, for example 1, 4, 5, 9

tails stays sorted, so each element costs O(log n) and the total is O(n log n).

Comparison with other approaches

Summary

• Time is states x transition cost; space is the states you keep at once.
• Knapsack DP is pseudo-polynomial because it depends on the numeric value of W.
• Memoization computes only reachable states but pays for recursion; tabulation is predictable and easy to optimize.
• Rolling arrays cut memory to one or two rows at the cost of reconstruction.