Remember the recursive Fibonacci from Unit 23, which made over a million calls for fib(30)? The problem wasn't recursion; it was solving the same subproblems again and again: fib(28) was worked out twice, fib(27) three times, and so on.

Dynamic programming (DP) is the technique of solving each subproblem once and reusing the answer. The simplest form is memoisation: keep a dictionary of answers, check it before doing any work, and store every answer you calculate:

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(30))
print(fib(300))

Each value from 0 to n is now computed once: O(n) instead of exponential. You saw in Unit 31 that functools.lru_cache does exactly this as a decorator; writing it out once shows what it's doing.