Introduction to Dynamic Programming

What you'll learn

Dynamic programming (DP) is the most powerful technique in this course. The idea is almost embarrassingly simple: when a problem breaks into smaller subproblems that overlap, solve each one only once and remember the answer. That single move can turn an exponential algorithm into a linear one.

By the end you'll be able to:

• Recognize the two properties that make a problem a DP problem
• Write both top-down (memoized) and bottom-up (tabulated) solutions
• Follow a repeatable 4-step recipe to design any DP

The problem with plain recursion

Take the Fibonacci numbers, where each is the sum of the previous two. The natural recursion is a one-liner — and a performance disaster:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # recomputes the same calls

The trouble is that fib(n - 1) and fib(n - 2) re-explore the same smaller calls again and again. Computing fib(5) already calls fib(2) three times; the total work grows like O(φⁿ) ≈ O(1.618ⁿ).

The two properties

Dynamic programming applies exactly when a problem has both of these:

• Overlapping subproblems. The same subproblems are solved many times (like fib(2) above). If every subproblem were distinct, there'd be nothing to reuse.
• Optimal substructure. An optimal answer is built from optimal answers to its subproblems — so combining sub-answers is valid.

Memoization: top-down

The smallest possible fix: keep the recursion, but cache each answer the first time you compute it. This is memoization — top-down DP. The shape of the code barely changes:

def fib(n, memo={}):
    if n < 2:
        return n
    if n not in memo:                     # compute only once
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Now each fib(k) is computed once and reused, so the running time collapses from exponential to O(n). The cost is an O(n) cache plus the recursion stack.

Tabulation: bottom-up

Flip it around: instead of recursing down from n, fill a table up from the base cases. This is tabulation — bottom-up DP. Watch the table fill, one cell at a time. Each new cell depends on the two before it (highlighted), which are already computed:

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # dependencies already filled
    return dp[n]

The DP recipe

Every dynamic program — no matter how advanced — is designed with the same four questions. Keep this checklist handy for the rest of the phase:

For Fibonacci: the state is dp[i] = the i-th number; the transition is dp[i] = dp[i-1] + dp[i-2]; the base cases are dp[0]=0, dp[1]=1; and the order is simply increasing i.

Complexity

Recap & quick check

You've got the core idea. Now let's drill the most common one-dimensional patterns until they're automatic. Next up: Module 16 — 1-D Dynamic Programming.