Lesson 3: Introduction to Dynamic Programming

The Forgetful Calculator

Imagine you ask your friend to compute Fibonacci(30). They don't remember any previous calculations, so they start from scratch. To compute Fibonacci(30), they need Fibonacci(29) and Fibonacci(28). To get Fibonacci(29), they need Fibonacci(28) again — and Fibonacci(27). They compute Fibonacci(28) twice. Then Fibonacci(27) three times. Then Fibonacci(26) five times.

By the time they reach Fibonacci(30), they've computed Fibonacci(10) hundreds of times — the exact same answer, over and over, thrown away each time.

Now imagine a smarter friend. Every time they compute a Fibonacci number, they write it down in a notebook. Next time someone asks for that same number, they just look it up instead of recalculating.

That notebook is dynamic programming. The technique of remembering answers so you never compute the same thing twice.

What Is Dynamic Programming?

Dynamic Programming (DP) is applicable when a problem has two properties:

1. Overlapping subproblems — the same subproblems are solved multiple times
2. Optimal substructure — the optimal solution to the whole problem can be built from optimal solutions to subproblems

"DP is recursion + memory. That's it. Everything else is just implementation."

If you can solve a problem recursively AND the recursion recomputes the same values, DP will make it dramatically faster.

The Naive Fibonacci: An O(2^n) Disaster

def fib_naive(n):
    if n <= 1:             # Base cases
        return n
    return fib_naive(n-1) + fib_naive(n-2)   # Recurse on both halves

What this looks like for fib(6):

                     fib(6)
                    /       \
               fib(5)       fib(4)
              /     \       /     \
          fib(4)  fib(3) fib(3) fib(2)
          /   \   /   \
       fib(3)fib(2)fib(2)fib(1)
       ...

fib(4) is computed twice, fib(3) is computed three times, fib(2) four times. The tree grows exponentially. For n = 50, this makes over 1 trillion calls.

Approach 1: Memoization (Top-Down DP)

Memoization caches the result of each function call. If you've already computed fib(n), return the cached result immediately.

from functools import lru_cache

@lru_cache(maxsize=None)           # Decorator auto-caches all return values
def fib_memo(n):
    if n <= 1:                     # Base cases (same as naive version)
        return n
    return fib_memo(n-1) + fib_memo(n-2)   # Recurse — but results are cached

# --- Example ---
print(fib_memo(10))    # Output: 55
print(fib_memo(50))    # Output: 12586269025  (instant, no timeout)
print(fib_memo(100))   # Output: 354224848179261915075

Output:

55
12586269025
354224848179261915075

Manual memoization (without decorator):

def fib_memo_manual(n, cache={}):
    if n in cache:                 # Check if answer already computed
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo_manual(n-1, cache) + fib_memo_manual(n-2, cache)
    return cache[n]                # Store result before returning

With memoization, each unique value of n is computed exactly once. The call tree collapses from exponential to linear: O(2^n) becomes O(n).

Approach 2: Tabulation (Bottom-Up DP)

Instead of starting from the top and caching as we go down, tabulation builds the answer from the ground up — filling a table from the smallest subproblems to the largest.

def fib_dp(n):
    if n <= 1:                     # Handle base cases directly
        return n

    dp = [0] * (n + 1)            # Create table with n+1 slots
    dp[1] = 1                      # Seed the base cases

    for i in range(2, n + 1):     # Fill table from index 2 to n
        dp[i] = dp[i-1] + dp[i-2] # Each value = sum of previous two

    return dp[n]                   # Answer is at the last position

# --- Example with trace ---
n = 8
result = fib_dp(n)
print(f"fib({n}) = {result}")

# Show the full table
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    dp[i] = dp[i-1] + dp[i-2]

print("dp table:", dp)

Output:

fib(8) = 21
dp table: [0, 1, 1, 2, 3, 5, 8, 13, 21]

Step-by-step table fill:

Index:  0  1  2  3  4  5  6  7   8
Value:  0  1  ?  ?  ?  ?  ?  ?   ?

Step 1: dp[2] = dp[1] + dp[0] = 1 + 0 = 1
Step 2: dp[3] = dp[2] + dp[1] = 1 + 1 = 2
Step 3: dp[4] = dp[3] + dp[2] = 2 + 1 = 3
Step 4: dp[5] = dp[4] + dp[3] = 3 + 2 = 5
Step 5: dp[6] = dp[5] + dp[4] = 5 + 3 = 8
Step 6: dp[7] = dp[6] + dp[5] = 8 + 5 = 13
Step 7: dp[8] = dp[7] + dp[6] = 13 + 8 = 21

Space Optimization: O(1) Space

Notice that dp[i] only depends on the previous two values. We don't need the entire table — just the last two numbers.

def fib_optimized(n):
    if n <= 1:
        return n

    prev2 = 0      # Represents dp[i-2]
    prev1 = 1      # Represents dp[i-1]

    for i in range(2, n + 1):
        current = prev1 + prev2    # Compute current value
        prev2 = prev1              # Slide the window forward
        prev1 = current

    return prev1

# --- Example ---
for i in range(10):
    print(f"fib({i}) = {fib_optimized(i)}")

Output:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34

This approach uses O(1) space — no table, no recursion stack, just two variables.

Performance Comparison

import time

def benchmark(func, n):
    start = time.time()
    result = func(n)
    elapsed = time.time() - start
    return result, elapsed

# fib_naive is too slow for n=40+, skip for large n
n = 35
_, t1 = benchmark(fib_naive, n)
_, t2 = benchmark(fib_memo, n)
_, t3 = benchmark(fib_dp, n)
_, t4 = benchmark(fib_optimized, n)

print(f"Naive:      {t1:.4f}s")
print(f"Memo:       {t2:.6f}s")
print(f"Tabulation: {t3:.6f}s")
print(f"Optimized:  {t4:.6f}s")

Approximate output (n=35):

Naive:      2.4831s
Memo:       0.000021s
Tabulation: 0.000018s
Optimized:  0.000012s

The naive approach takes seconds while all DP versions complete in microseconds.

How to Identify DP Problems

Ask yourself these questions:

1. Can I solve this recursively? If yes, keep going.
2. Does the recursion solve the same subproblems multiple times? If yes, this is overlapping subproblems — DP can help.
3. Can I express the answer to a bigger problem in terms of answers to smaller problems? This is optimal substructure.

Common problem shapes that hint at DP:

• "Find the maximum/minimum of something"
• "Count the number of ways to..."
• "Is it possible to reach/achieve...?"
• "What is the longest/shortest sequence that..."

Memoization vs Tabulation

The Three-Step DP Framework

For any DP problem, follow this structure:

Step 1 — Define the state: What does dp[i] represent?

• For Fibonacci: dp[i] = the i-th Fibonacci number

Step 2 — Find the recurrence: How does dp[i] relate to smaller subproblems?

• For Fibonacci: dp[i] = dp[i-1] + dp[i-2]

Step 3 — Handle base cases: What are the smallest subproblems with known answers?

• For Fibonacci: dp[0] = 0, dp[1] = 1

This framework works for every DP problem, from Fibonacci to Knapsack to Longest Common Subsequence.

Interview Relevance

Dynamic programming is consistently rated as the hardest and most important topic in software engineering interviews. Companies like Google, Meta, Amazon, and Microsoft use DP problems to separate candidates who can only memorize patterns from those who genuinely understand algorithmic thinking.

The good news: once you understand memoization and tabulation deeply — not just Fibonacci, but why they work — you can approach any new DP problem systematically rather than hoping you've seen it before.

In the next lesson, we'll apply this framework to three classic problems: 0/1 Knapsack, Longest Common Subsequence, and Coin Change.