Dynamic Programming & Greedy Algorithms

TL;DR

You'll learn to spot when a problem has overlapping subproblems (DP) versus a locally-optimal-choice structure (greedy). You'll practice converting recursive brute force into memoized and tabulated solutions, and learn the classic greedy proof pattern: exchange argument. By the end, you can pick the right tool fast on sight, not by guessing.

1. The Mental Model

DP solves a problem by combining answers to smaller versions of itself, and it saves those answers so it never recomputes them. Greedy solves a problem by making the best-looking choice right now and never looking back. DP is for when today's choice depends on tomorrow's possibilities; greedy is for when today's choice can be proven safe forever. If you can't prove a local choice is always safe, don't trust greedy — fall back to DP.

2. The Core Material

2.1 Recognizing DP: overlapping subproblems + optimal substructure

Photo by Steve A Johnson on Pexels

A problem is a DP candidate when two things hold. First, optimal substructure: the best answer to the whole problem is built from the best answers to subproblems. Second, overlapping subproblems: naive recursion recomputes the same subproblem many times. Fibonacci is the textbook case — fib(5) calls fib(3) twice, fib(2) three times, and so on. Without memoization, you get exponential time; with it, linear.

import functools

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

# cleaner with built-in caching
@functools.lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

Top-down (memoization) keeps the recursive shape but caches results. Bottom-up (tabulation) builds a table from the base case upward, avoiding recursion overhead and stack limits — important on Leetcode where n can be 10⁴+ and recursion depth errors are a real failure mode.

def fib_tab(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 workflow for any DP problem is always the same four questions:
1. What does dp[i] (or dp[i][j]) actually represent?
2. What's the recurrence — how does dp[i] relate to smaller states?
3. What's the base case?
4. What order do I fill the table in (so dependencies are already computed)?

2.2 1D and 2D DP patterns

Photo by Steve A Johnson on Pexels

1D DP — House Robber. You can't rob two adjacent houses. dp[i] = max money robbable from houses 0..i. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip house i (take dp[i-1]) or rob it (take dp[i-2] plus its value).

def rob(nums):
    prev2, prev1 = 0, 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1

Notice you don't need the full array — just the last two values. This space optimization (O(n) memory to O(1)) is something interviewers actively look for.

2D DP — Longest Common Subsequence (LCS). dp[i][j] = length of LCS of text1[:i] and text2[:j]. If characters match, extend the diagonal; otherwise take the best of dropping one character from either string.

def longestCommonSubsequence(text1, text2):
    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]

2D grid DP (like Unique Paths or Edit Distance) follows the exact same discipline: define the cell, write the recurrence, fix the base row/column, fill in the right order (usually row by row, left to right).

2.3 Greedy: the exchange argument and when it actually fails

Greedy only works when you can prove that swapping any optimal solution's choice for the greedy choice never makes things worse — that's the exchange argument. The classic working example: Activity Selection. Given intervals, pick the max number of non-overlapping ones. Greedy rule: always pick the interval that finishes earliest among remaining options.

def max_activities(intervals):
    intervals.sort(key=lambda x: x[1])  # sort by end time
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Why does "earliest finish" work? Suppose an optimal solution picks some other interval instead of the earliest-finishing one. You can always swap it in — it finishes no later, so it can't block any future interval that the other choice didn't already block. That swap never hurts, so greedy is safe.

Contrast this with 0/1 Knapsack, where greedy (pick highest value/weight ratio first) fails. Counter-example: capacity 10, items (weight 6, value 30) and (weight 5, value 25) + (weight 5, value 25). Greedy by ratio picks item 1 (ratio 5.0) for value 30, but the optimal is both other items for value 50. The failure happens because taking an item isn't reversible and doesn't leave "room" the way interval scheduling does — there's no valid exchange argument. That's your signal: when you can't construct an exchange argument, the problem is DP, not greedy.

flowchart TD
    A["Does today's choice affect which future choices are available?"] -->|No, choices are independent / provably safe locally| B["Greedy: pick locally best, move on"]
    A -->|Yes, future options depend on exact past choices| C["Overlapping subproblems?"]
    C -->|Yes| D["DP: define state, recurrence, base case"]
    C -->|No, no repeated work| E["Plain recursion / divide & conquer"]
    B --> F["Prove with exchange argument before trusting it"]

3. Worked Example

Problem: Coin Change (Leetcode 322). Given coins [1, 2, 5] and target amount 11, find the minimum number of coins to make it, or -1 if impossible.

First instinct: greedy — always take the biggest coin that fits. For 11: take 5, remainder 6; take 5, remainder 1; take 1. That's 3 coins — and it happens to be correct here. But try coins [1, 3, 4] with amount 6: greedy takes 4, then two 1s — 3 coins. The optimal is 3 + 3 — 2 coins. Greedy fails because there's no exchange argument: taking a 4 doesn't leave you better positioned than taking two 3s. So this problem is DP.

Define dp[a] = minimum coins to make amount a. Recurrence: dp[a] = min(dp[a - c] + 1 for c in coins if c <= a). Base case: dp[0] = 0.

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

print(coinChange([1, 3, 4], 6))   # 2
print(coinChange([1, 2, 5], 11))  # 3

Trace for amount 6 with coins [1, 3, 4]: dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=1, dp[5]=2, dp[6]=2 (via dp[3]+1 or dp[2]+1 — both give 2). Matches the expected optimal answer, confirming DP beats greedy here.

4. Production Pitfalls & Best Practices

4.1 Real-World Best Practices

• Always state the dp[i] definition in a comment before coding — half of all bugs come from an ambiguous state definition.
• Space-optimize after correctness, not before. Get the 2D table working, then collapse to rolling 1D arrays once the recurrence only needs the last row or two.
• Sort first when greedy depends on order (by end time, by ratio, by deadline) — nearly every greedy solution starts with a sort() call.
• Use lru_cache for quick top-down prototypes, then convert to iterative tabulation for final submission to avoid Python recursion limits (default 1000).
• Initialize DP arrays with the correct "impossible" sentinel (float('inf') for minimization, float('-inf') or 0 for maximization) — mixing these up silently corrupts results.
• Write the brute-force recursion first, confirm it's correct on small inputs, then add memoization — don't jump straight to tabulation.

4.2 Common Bugs & Anti-Patterns

Bug 1 — off-by-one in table size.

# BAD: dp sized to n instead of n+1, crashes on dp[n]
dp = [0] * n

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

Bug 2 — mutable default argument in memoization.

# BAD: dict persists across calls, stale cache
def f(n, memo={}):
    ...

# FIXED: fresh cache per call, or use lru_cache
def f(n, memo=None):
    if memo is None:
        memo = {}
    ...

Bug 3 — applying greedy without checking the exchange argument.

# BAD: greedy ratio pick for 0/1 knapsack — wrong answer
items.sort(key=lambda x: x.value / x.weight, reverse=True)

# FIXED: use DP since items aren't divisible and choices aren't reversible
dp = [[0] * (capacity + 1) for _ in range(len(items) + 1)]
# fill with 0/1 knapsack recurrence

Bug 4 — forgetting base case initialization in 2D grid DP.

# BAD: dp[0][0] left at default 0 when it should reflect a blocked start
dp = [[0] * n for _ in range(m)]

# FIXED: explicitly set base row/column before the loop
dp[0][0] = 1 if grid[0][0] == 0 else 0
for j in range(1, n):
    dp[0][j] = dp[0][j - 1] if grid[0][j] == 0 else 0

4.3 When to Use What

5. Now Try It

Solve Leetcode 198 (House Robber) right here, then extend it: write rob_with_indices(nums) that returns both the max money and the list of house indices chosen. Test it on nums = [2, 7, 9, 3, 1] — expected max is 12 (houses at indices 0, 2, 4). Then try to break greedy: write a greedy version that always robs the higher-value house among any two adjacent options, and find an input where it gives a wrong answer.

Success looks like: your DP function returns 12 and the correct index list for the test case, and you've found at least one concrete input array where greedy disagrees with DP.