The Core Idea

Dynamic Programming (DP) = recursion + memoization. It solves problems by:

  1. Breaking them into overlapping subproblems (same subproblems repeat)

  2. Solving each subproblem ONCE and caching the result

  3. Building up to the final answer

Two Approaches

Top-Down (Memoization)

Start with the original problem, recurse into subproblems, cache results.

from functools import lru_cache

@lru_cache(maxsize=None)  # Python's built-in memoization decorator
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Bottom-Up (Tabulation)

Start with the smallest subproblems, build up to the answer using a table.

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)  # Table to store subproblem results
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

When Does DP Apply?

Two conditions:

  1. Optimal substructure: Optimal solution uses optimal solutions to subproblems

  2. Overlapping subproblems: Same subproblems are solved multiple times

The DP Problem-Solving Framework

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

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

  3. Set base cases: What are the trivial answers?

  4. Choose direction: Top-down or bottom-up?

  5. Optimize space: Can you reduce from O(n) to O(1)?

Exercises