Dynamic programming

Some recursive solutions do the same work again and again. The Fibonacci numbers are the classic: each is the sum of the two before (0, 1, 1, 2, 3, 5, 8…). Written directly, fib(n) calls fib(n - 1) and fib(n - 2), which call smaller ones, and the same values get worked out millions of times. fib(40) makes over 300 million calls.

Dynamic programming fixes this by remembering. Memoization stores each answer the first time it's worked out (in a dictionary, say), and looks it up after that. In Python, the functools.cache decorator does it for you.

from functools import cache

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

print(fib(40))

Now each fib(k) is worked out once, so the whole thing is O(n). The other style builds the answers bottom-up in a table, from the smallest case upwards, with a plain loop.

def fib_table(n):
    table = [0, 1]
    for i in range(2, n + 1):
        table.append(table[i - 1] + table[i - 2])
    return table[n]

print(fib_table(10))

It works whenever a problem breaks into smaller problems that overlap: the fewest coins to make an amount, the cheapest route across a grid, how similar two words are (spell checkers), or which items fit best in a bag of limited size.