Dynamic programming introduction

Dynamic programming

Dynamic programming (DP) is a fancy name for a simple idea: don't solve the same subproblem twice. When a problem breaks into overlapping subproblems, you solve each one once, remember the answer, and reuse it.

When does DP apply?

Two ingredients:

Optimal substructure — the answer is built from answers to smaller versions of the same problem.
Overlapping subproblems — those smaller problems recur many times.

The naive recursive Fibonacci has both: fib(n) = fib(n-1) + fib(n-2), and it recomputes fib(2) an exponential number of times. DP fixes the recomputation.

The recursion → DP recipe

Write the plain recursion (define the subproblem and the base cases).
Notice it recomputes the same inputs.
Memoize — cache each result by its arguments and return the cache on a repeat.

memo = {}
function fib(n):
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

That one cache turns O(2ⁿ) into O(n): each subproblem is computed once.

The pay-off

DP collapses exponential brute force into polynomial time. The hard part is never the caching — it's defining the subproblem: what does solve(x) mean, what are its arguments, and how does it combine smaller answers? Nail that, and memoization is mechanical. The next lesson contrasts the two standard ways to implement it.