Memoization and overlapping subproblems

Dynamic programming relies on a simple idea: when a problem breaks down into subproblems that REPEAT (they are said to overlap), each subproblem only needs to be computed once, then memoized (stored) in a dictionary or an array. The next time it is needed, it is simply read back instead of being recomputed. This technique is called memoization.

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

With this version, each value fib(k) is computed only once, then stored in memo. The call tree no longer "re-explodes": as soon as an already-seen subproblem reappears, it is read from memory instead of descending back into the branches.

fib_memo(5): actual tree of COMPUTATIONS (not simple lookups)

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)   (computed)
        fib(0)   (computed)
      fib(1)      (read from memory, not recomputed)
    fib(2)        (read from memory, not recomputed)
  fib(3)          (read from memory, not recomputed)

only 6 actual computations (fib(0) to fib(5)), the rest is read in O(1)

This principle of "overlapping subproblems" is the key condition for applying dynamic programming: if subproblems never repeat, memoizing is useless (this is the case, for example, with merge sort, where each sub-array is different). With memoization, Fibonacci goes from exponential complexity to linear complexity O(n): each value from 0 to n is computed exactly once.