Dynamic Programming: Introduction

Dynamic programming (DP) solves each repeated subproblem once and remembers the answer. It turns exponential recursion into polynomial table filling.

When DP works

• Optimal substructure: the optimal answer to a big problem is built from optimal answers to smaller ones.
• Overlapping subproblems: the same small problem shows up again and again.

In divide and conquer the parts are independent; here they repeat. Unlike greedy, DP considers all subproblem answers and needs no proof that a local choice is safe.

Naive recursion is exponential

calls = 0

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

print(fib(20), calls)
calls = 0
fib(25)
print("fib(25) calls:", calls)

fib(20) makes 21 891 calls and fib(25) makes 242 785: about O(1.6^n).

Top-down: memoization