🧩 Dynamic Programming

The pattern that separates senior from junior engineers in interviews.

TL;DR

DP = Recursion + Memoization (remember past results)

Used when:

1. Overlapping subproblems - Same calculations repeated
2. Optimal substructure - Optimal solution built from optimal sub-solutions

Brute force O(2^n) → DP O(n) or O(n²)

The Mental Model

Without DP (Fibonacci)

                    fib(5)
                   /      \
              fib(4)      fib(3)
             /    \       /    \
         fib(3)  fib(2) fib(2) fib(1)
         /   \
      fib(2) fib(1)
      
Redundant: fib(3) computed twice, fib(2) computed three times
Time: O(2^n) 😱

With DP

fib(5) → fib(4) → fib(3) → fib(2) → fib(1) → fib(0)
                    ↓          ↓
                 cached!    cached!
                 
Time: O(n) ✓

---

Two Approaches

1. Top-Down (Memoization)

Recursion + Cache

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

2. Bottom-Up (Tabulation)

Iteration + Table

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

Space-Optimized:

def fib(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

---

The DP Framework

Step 1: Define State

What does dp[i] (or dp[i][j]) represent?

Examples:

• dp[i] = minimum cost to reach step i
• dp[i] = number of ways to make sum i
• dp[i][j] = longest common subsequence of s1[0:i] and s2[0:j]

Step 2: Find Base Case

What's the smallest subproblem?

Examples:

• dp[0] = 0 (starting point)
• dp[0] = 1 (one way to do nothing)
• dp[i][0] = 0 (comparing with empty string)

Step 3: Write Recurrence

How to build dp[i] from smaller subproblems?

dp[i] = f(dp[i-1], dp[i-2], ...)

Step 4: Determine Order

Bottom-up: compute smaller subproblems first Top-down: recursion handles order automatically

Step 5: Locate Answer

Where is the final result?

• Usually dp[n] or dp[n-1]
• Sometimes max(dp) or dp[m][n]

---

Pattern 1: 1D DP (Single Sequence)

Problem: Climbing Stairs

Ways to climb n stairs (1 or 2 steps at a time)

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    
    prev, curr = 1, 2
    
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

# n=5: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 
#      1+2+2, 2+1+2, 2+2+1 = 8 ways

State: dp[i] = ways to reach step i Recurrence: dp[i] = dp[i-1] + dp[i-2] Why? To reach step i, either from i-1 (1 step) or i-2 (2 steps)

---

Problem: House Robber

Max money robbing non-adjacent houses

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev, curr = nums[0], max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        prev, curr = curr, max(curr, prev + nums[i])
    
    return curr

# nums = [2, 7, 9, 3, 1]
# dp[0] = 2
# dp[1] = max(2, 7) = 7
# dp[2] = max(7, 2+9) = 11 (rob house 0 and 2)
# dp[3] = max(11, 7+3) = 11
# dp[4] = max(11, 11+1) = 12 (rob house 0, 2, 4)

State: dp[i] = max money from houses 0 to i Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) Why? Either skip house i (take dp[i-1]) or rob house i (take dp[i-2] + nums[i])

---

Problem: Coin Change

Minimum coins to make amount

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# coins = [1, 2, 5], amount = 11
# dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1 (use one 5-coin)
# dp[11] = dp[6]+1 = dp[1]+1+1 = 3 (5+5+1)

State: dp[i] = min coins to make amount i Recurrence: dp[i] = min(dp[i - coin] + 1) for each coin

---

Pattern 2: 2D DP (Two Sequences / Grid)

Problem: Unique Paths

Count paths from top-left to bottom-right (only right/down)

def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

# 3x3 grid:
# [1, 1, 1]
# [1, 2, 3]
# [1, 3, 6]  → 6 paths

State: dp[i][j] = paths to cell (i, j) Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]

---

Problem: Longest Common Subsequence (LCS)

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

# text1 = "abcde", text2 = "ace" → LCS = "ace" = 3

State: dp[i][j] = LCS of text1[0:i] and text2[0:j] Recurrence:

• If chars match: dp[i][j] = dp[i-1][j-1] + 1
• Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

---

Problem: Edit Distance

Minimum operations to convert word1 to word2

def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases: empty string
    for i in range(m + 1):
        dp[i][0] = i  # Delete all chars
    for j in range(n + 1):
        dp[0][j] = j  # Insert all chars
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # No operation
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Delete
                    dp[i][j-1],    # Insert
                    dp[i-1][j-1]   # Replace
                )
    
    return dp[m][n]

# "horse" → "ros" = 3 (replace h→r, remove r, remove e)

---

Pattern 3: Knapsack

0/1 Knapsack

Max value with weight limit (each item once)

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Don't take item i
            dp[i][w] = dp[i-1][w]
            
            # Take item i (if it fits)
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1])
    
    return dp[n][capacity]

Unbounded Knapsack (Coin Change II)

Count ways to make amount (unlimited coins)

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]

---

Pattern 4: State Machine

Best Time to Buy and Sell Stock (with cooldown)

def max_profit(prices: list[int]) -> int:
    if len(prices) < 2:
        return 0
    
    # States: hold, sold, rest
    hold = -prices[0]  # Holding stock
    sold = 0           # Just sold
    rest = 0           # Not holding, can buy
    
    for price in prices[1:]:
        prev_hold = hold
        hold = max(hold, rest - price)  # Keep holding or buy
        rest = max(rest, sold)          # Keep resting or cooldown
        sold = prev_hold + price        # Sell
    
    return max(sold, rest)

---

DP Decision Flowchart

---

Top Interview DP Problems

Problem	Type	Difficulty
Climbing Stairs	1D	Easy
House Robber	1D	Medium
Coin Change	Knapsack	Medium
Longest Increasing Subsequence	1D	Medium
Unique Paths	2D Grid	Medium
Longest Common Subsequence	2D	Medium
Edit Distance	2D	Medium
Word Break	1D + Set	Medium
Decode Ways	1D	Medium
Best Time Buy/Sell Stock III	State Machine	Hard
Regular Expression Match	2D	Hard

---

Quick Reference

# 1D DP Template
dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
    dp[i] = f(dp[i-1], dp[i-2], ...)
return dp[n]

# 2D DP Template
dp = [[0] * (n+1) for _ in range(m+1)]
# Base cases
for i in range(1, m+1):
    for j in range(1, n+1):
        if condition:
            dp[i][j] = dp[i-1][j-1] + something
        else:
            dp[i][j] = max/min(dp[i-1][j], dp[i][j-1])
return dp[m][n]

---

---

Next: Greedy Pattern → - When local optimal is global optimal.