16. Dynamic Programming

Dynamic programming (DP) is the hardest topic in DSA interviews. Not because the code is complex — most DP solutions are short. It's hard because recognizing that a problem is DP, defining the state, and finding the recurrence requires a mental shift. This lesson gives you the framework to identify and approach DP problems.

The Core Idea

DP solves problems by breaking them into overlapping subproblems and storing results so you never solve the same subproblem twice.

Fibonacci without DP:
fib(5) → fib(4) + fib(3)
         fib(3) + fib(2)   fib(2) + fib(1)
         fib(2) + fib(1)   ...

fib(3) is computed twice. fib(2) is computed three times.
Without caching: O(2ⁿ). With caching: O(n).

Two requirements for DP to apply:

1. Optimal substructure — the optimal solution contains optimal solutions to subproblems
2. Overlapping subproblems — the same subproblems are solved multiple times

If subproblems don't overlap, it's just divide-and-conquer (like merge sort). If there's no optimal substructure, DP won't help.

Memoization vs Tabulation

Two ways to implement DP:

Memoization (top-down) — recursive, cache results as you go. Python's @cache decorator makes this trivial:

from functools import cache

@cache
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

That's it. @cache (or @lru_cache(maxsize=None)) stores every call's result automatically. No manual dictionary management.

Tabulation (bottom-up) — iterative, fill a table from smallest subproblems up. No recursion.

def fib(n: int) -> int:
    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]

Both are O(n) time, O(n) space. Tabulation avoids recursion depth limits (Python's default is 1000).

Space optimization — when you only need the last 1-2 values, drop the array:

def fib(n: int) -> int:
    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

Every DP problem follows this pattern:

1. Define the state — what does dp[i] (or dp[i][j]) represent?
2. Find the recurrence — how does dp[i] relate to smaller subproblems?
3. Set base cases — what are the trivial answers?
4. Determine the order — fill the table so dependencies are already computed
5. Extract the answer — usually dp[n] or dp[n][m]

Classic Example: Climbing Stairs

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

LeetCode 70 - Climbing Stairs

# Top-down with @cache
@cache
def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    return climb_stairs(n - 1) + climb_stairs(n - 2)

# Bottom-up with space optimization
def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    prev, curr = 1, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

This is literally Fibonacci. Many DP problems reduce to known patterns once you define the state correctly.

Classic Example: Coin Change

Given coins of different denominations, find the minimum number of coins to make a target amount.

LeetCode 322 - Coin Change

# Top-down
@cache
def coin_change_memo(coins: tuple, amount: int) -> int:
    if amount == 0:
        return 0
    if amount < 0:
        return float('inf')
    return 1 + min(coin_change_memo(coins, amount - c) for c in coins)

# Bottom-up (preferred — no recursion limit)
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

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

Common DP Categories

Knapsack: 0/1 vs Unbounded

0/1 Knapsack — each item used at most once. Iterate capacity right-to-left so you don't reuse items.

LeetCode 416 - Partition Equal Subset Sum

# Can we make target sum using each number at most once?
def can_partition(nums: list[int], target: int) -> bool:
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):  # RIGHT to LEFT
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

Unbounded Knapsack — each item used unlimited times. Iterate left-to-right so items can be reused.

# Coin change — each coin can be used unlimited times
for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], dp[i - coin] + 1)  # LEFT to RIGHT

The direction matters: right-to-left uses the previous row's values (item not yet used). Left-to-right uses the current row's values (item already available for reuse).

2D Grid DP

Grid problems where you can only move right or down. Each cell depends on the cell above and to the left.

LeetCode 62 - Unique Paths

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]  # from above + from left
    return dp[m - 1][n - 1]

Or with @cache for a cleaner top-down approach:

@cache
def unique_paths(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1
    return unique_paths(m - 1, n) + unique_paths(m, n - 1)

String DP: Longest Common Subsequence

Find the longest subsequence common to both strings. A subsequence doesn't need to be contiguous — characters can be apart but must stay in order.

LeetCode 1143 - Longest Common Subsequence

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  # both chars match, extend
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # skip one char
    return dp[m][n]

Or with @cache:

from functools import cache

def longest_common_subsequence(text1: str, text2: str) -> int:
    @cache
    def dp(i: int, j: int) -> int:
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + dp(i + 1, j + 1)
        return max(dp(i + 1, j), dp(i, j + 1))
    return dp(0, 0)

dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]. If characters match, take it and move both forward. If not, try skipping one from either string.

String DP: Edit Distance

Minimum insertions, deletions, and replacements to transform one string into another.

LeetCode 72 - Edit Distance

def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i  # delete all characters
    for j in range(n + 1):
        dp[0][j] = j  # insert all characters

    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 edit needed
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # replace
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                )
    return dp[m][n]

Or with @cache:

@cache
def min_distance(word1: str, word2: str) -> int:
    if not word1:
        return len(word2)
    if not word2:
        return len(word1)
    if word1[-1] == word2[-1]:
        return min_distance(word1[:-1], word2[:-1])
    return 1 + min(
        min_distance(word1[:-1], word2[:-1]),  # replace
        min_distance(word1[:-1], word2),       # delete
        min_distance(word1, word2[:-1]),        # insert
    )

State Design

The hardest part of DP is choosing the right state. Tips:

• Start with brute force — what decisions are you making? Those become your state variables.
• Ask "what do I need to know at step i?" — that's your state.
• If stuck, add dimensions — dp[i] not enough? Try dp[i][j]. Too many dimensions? Look for ways to compress.

Example thought process for House Robber:

• At house i, I choose: rob or skip.
• If I rob house i, I can't rob house i-1.
• State: dp[i] = max money robbing houses 0..i.
• Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

@cache vs Tabulation — When to Use Which

Tip: start with @cache to verify correctness, then convert to tabulation if needed for performance or to avoid recursion limits. Use sys.setrecursionlimit() as a last resort.

How to Recognize DP

Look for these signals:

• "Count the number of ways" → likely DP
• "Find the minimum/maximum" with choices at each step → likely DP
• "Can you reach / is it possible" with overlapping paths → likely DP
• Problem has optimal substructure (best solution uses best sub-solutions)
• Brute force would try all combinations (exponential)

Not DP if:

• Greedy works (each local choice is globally optimal)
• No overlapping subproblems (divide-and-conquer instead)
• The problem is about a single traversal or scan

DP vs Greedy

If greedy works, use it — it's faster. DP is the fallback when greedy doesn't guarantee optimality.

Practice Problems

Key Takeaways

• DP = overlapping subproblems + optimal substructure — cache results to avoid recomputation
• @cache makes top-down DP trivial in Python — one decorator, no manual memoization
• Tabulation (bottom-up) avoids recursion limits and is easier to space-optimize
• The framework: define state → find recurrence → set base cases → fill table → extract answer
• Common patterns: 1D linear, knapsack, 2D grid, strings, intervals
• 0/1 knapsack iterates right-to-left; unbounded iterates left-to-right
• "Count ways," "find min/max with choices," "is it possible" → think DP
• If greedy works, prefer it over DP — DP is the fallback for when local choices aren't globally optimal
• Start with @cache for correctness, convert to tabulation for production