Concepts

Dynamic programming (DP) is a way of solving a problem by breaking it into smaller subproblems, solving each subproblem once, storing the answer, and reusing it whenever the same subproblem comes up again. The name comes from Richard Bellman, who developed the method in the 1950s; "programming" here means planning with a table, not writing code. This chapter explains when DP applies, the two properties that make it work, and the vocabulary used in the rest of the guide.

Two properties that make DP work

A problem is a good fit for DP when it has both of these properties.

• Overlapping subproblems: a naive recursive solution solves the same subproblem many times. Storing each result turns repeated work into a table lookup.
• Optimal substructure: an optimal answer for the whole problem can be built from optimal answers to its subproblems. The shortest path from A to C through B contains the shortest path from A to B, for example.

Divide and conquer also splits a problem into subproblems, but in merge sort the halves never overlap, so there is nothing to reuse. Greedy algorithms also rely on optimal substructure, but they commit to one locally best choice at each step; DP instead considers every choice and keeps the best one, which is why it works on problems where greedy fails.

Seeing the overlap: Fibonacci

The Fibonacci numbers are defined by F(0) = 0, F(1) = 1 and F(n) = F(n-1) + F(n-2). Translating the definition directly into code works, but it is extremely slow because the same values are recomputed again and again.

calls = 0


def fib(n: int) -> int:
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(25), calls)  # 75025 242785

Computing F(25) takes almost a quarter of a million calls, and the count grows roughly like 1.6^n. Yet there are only 26 distinct subproblems, F(0) through F(25). That gap between "calls made" and "distinct subproblems" is exactly what DP removes.

Two ways to remember answers

Memoization (top-down) keeps the recursive structure and adds a cache. The first call for a given argument computes the result; later calls return the stored value. In Python, functools.cache does this with one decorator.

from functools import cache


@cache
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(90))           # 2880067194370816120
print(fib.cache_info())  # CacheInfo(hits=88, misses=91, maxsize=None, currsize=91)

Tabulation (bottom-up) removes recursion entirely. You decide an order in which every subproblem's dependencies are already solved, then fill a table in that order with a loop.