Dynamic Programming

DP has a reputation for being hard, but it's really just "smart recursion." Instead of solving the same subproblem over and over, you solve it once and remember the answer. That's it.

The Core Idea

Break your problem into smaller subproblems. Solve those. Combine the answers. The magic is that subproblems overlap - the same smaller problem appears many times, so remembering answers saves massive time.

Two Approaches

1. Top-Down (Memoization)

Start from the main problem, recurse down, cache results:

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

2. Bottom-Up (Tabulation)

Start from the smallest subproblems, build up:

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

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

The DP Recipe

1. Define the subproblem - What does dp[i] represent?
2. Find the recurrence - How does dp[i] relate to smaller subproblems?
3. Identify base cases - What are the smallest subproblems?
4. Decide the order - Which subproblems to solve first?
5. Extract the answer - Where is the final answer?

Classic Example: Climbing Stairs

You can climb 1 or 2 steps. How many ways to reach step n?

def climbStairs(n):
    if n <= 2:
        return n

    # dp[i] = ways to reach step i
    prev1, prev2 = 1, 2

    for i in range(3, n + 1):
        curr = prev1 + prev2  # From i-1 or i-2
        prev1, prev2 = prev2, curr

    return prev2