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.

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


print(fib(90))  # 2880067194370816120

Both versions compute each of the n + 1 values once, so both run in O(n) time. Memoization is usually quicker to write and only visits states that are actually reachable. Tabulation avoids recursion depth limits and function call overhead, and it makes space optimizations easier to see.

Vocabulary

When to reach for DP

Look for DP when a problem asks for one of these and the input is small enough for a table of states to fit in memory.

• The minimum or maximum of something: fewest coins, cheapest path, largest value in a bag.
• The number of ways to do something: paths in a grid, ways to climb stairs, ways to decode a string.
• Whether something is possible at all: can a set be split into two equal sums, can a string be segmented into dictionary words.

A strong hint is a solution that makes a sequence of choices, where after each choice the rest of the problem looks like a smaller copy of the original. If two different sequences of choices can lead to the same remaining problem, you have overlapping subproblems.

Summary

• DP solves each distinct subproblem once and reuses the stored answer.
• It needs overlapping subproblems and optimal substructure.
• Memoization adds a cache to recursion; tabulation fills a table in dependency order.
• Every DP solution is described by its state, recurrence, base cases, evaluation order and final answer.