Pattern 07 · Dynamic Programming

Dynamic Programming

Break a problem into overlapping subproblems, solve each one exactly once, and store the results. The recipe that collapses exponential recursion trees into linear tables.

approaches memo · tableframework 5 stepscategories 5practice 20 problems

01 core concept

Stop solving the same subproblem twice

Naive recursion revisits the same states over and over — fib(3) twice, fib(2) three times. Cache each answer the first time you compute it and the exponential tree collapses to one call per unique state.

Fibonacci WITHOUT memoization (exponential -- repeated work): fib(5) / \ fib(4) fib(3) <-- fib(3) computed TWICE / \ / \ fib(3) fib(2) fib(2) fib(1) <-- fib(2) computed THREE times / \ fib(2) fib(1) Fibonacci WITH memoization (linear -- each subproblem solved once): fib(5) / \ fib(4) fib(3) [CACHED] / \ fib(3) fib(2) [CACHED] / \ fib(2) fib(1) Only 5 unique calls instead of 15.

The two properties that make it DP

Optimal substructure — the optimal solution to the problem contains optimal solutions to its subproblems.
Overlapping subproblems — the same subproblems appear multiple times in the recursion tree.

If only property 1 holds

No overlap means nothing to cache — use greedy or divide and conquer instead.

step 1 / 7walkthrough — house robber, dp table filling

houses [2, 7, 9, 3, 1]

rule no two adjacent

Houses hold [2, 7, 9, 3, 1]; robbing two adjacent ones trips the alarm. State: dp[i] = max loot from houses 0..i. Transition: dp[i] = max(dp[i−1], dp[i−2] + nums[i]). The cells are the dp table — empty for now.

or use arrow keys

02 two approaches

Top-down vs. bottom-up

ATop-down — memoization

Think recursively, cache results.

top_down_lru.pypython

# Template using @lru_cache
from functools import lru_cache

def solve(nums):
    @lru_cache(maxsize=None)
    def dp(i):
        if i == 0:                   # Base case
            return base_value
        # Transition: combine subproblems
        return best(dp(i - 1), dp(i - 2), ...)

    return dp(n)

top_down_dict.pypython

# Template using dict memo
def solve(nums):
    memo = {}

    def dp(state):
        if state in memo:
            return memo[state]
        if is_base_case(state):
            return base_value

        result = compute_from_subproblems(state)
        memo[state] = result
        return result

    return dp(initial_state)

BBottom-up — tabulation

Build the answer iteratively from base cases.

bottom_up.pypython

def solve(nums):
    n = len(nums)
    dp = [0] * (n + 1)

    # Base case
    dp[0] = base_value

    # Fill table
    for i in range(1, n + 1):
        dp[i] = best(dp[i - 1], dp[i - 2], ...)

    return dp[n]

Bottom-up table fill direction: dp[0] --> dp[1] --> dp[2] --> ... --> dp[n] base build build answer case from from dp[0] dp[0],dp[1]

Which one?

Top-down if states are sparse or the recursion is natural. Bottom-up if you need all states anyway or want space optimization.

03 the framework

The 5-step framework — use it for every DP problem

Step	Question	Example (Climbing Stairs)
1	Define STATE	dp[i] = number of ways to reach step i
2	Define TRANSITION	dp[i] = dp[i-1] + dp[i-2]
3	Define BASE CASE	dp[0] = 1, dp[1] = 1
4	Define ANSWER	dp[n]
5	Optimize SPACE	Only need dp[i-1] and dp[i-2] → O(1)

04 recognition

When to reach for it

"Find the minimum / maximum cost / value / count."
"How many ways to reach a target?"
"Is it possible to achieve X?"
"Find the longest / shortest subsequence / substring."
The problem has choices at each step, and choices affect future options.
Brute force would be exponential (try all combinations).

Can you define dp[i] or dp[i][j]? | +-- What does dp[i] represent? | | | +-- Count of ways? --> Addition in transition | +-- Min/max value? --> min()/max() in transition | +-- True/false? --> OR/AND in transition | +-- What are the transitions? | | | +-- dp[i-1] only? --> Linear, O(1) space possible | +-- dp[i-1] and dp[i-2]? --> Linear, O(1) space possible | +-- dp[i-coin] for coins? --> Knapsack variant | +-- dp[i-1][j-1], etc.? --> 2D, possibly O(n) space | +-- Top-down or Bottom-up? | +-- Top-down if: states sparse, recursion natural +-- Bottom-up if: need all states, want space optimization

When NOT to use it

If the subproblems don't overlap — optimal substructure alone isn't enough — there's nothing to cache. Use greedy or divide and conquer instead.

05 the five categories

DP categories you'll actually meet

C1Linear DP

State depends on previous element(s) in a 1-D sequence.

climb_stairs.py — LC 70python

def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

House Robber (LC 198) — the skip/take decision traced in the walkthrough above: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

house_robber.py — LC 198python

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = 0, 0
    for num in nums:
        curr = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = curr
    return prev1

C2Grid DP

State is a position in a 2-D grid — Unique Paths (LC 62): dp[i][j] = dp[i-1][j] + dp[i][j-1].

Grid (3x4): S = start, E = end, numbers = ways to reach cell +----+----+----+----+ | S | 1 | 1 | 1 | | 1 | | | | +----+----+----+----+ | 1 | 2 | 3 | 4 | | | | | | +----+----+----+----+ | 1 | 3 | 6 | 10 | | | | | E | +----+----+----+----+ dp[i][j] = dp[i-1][j] + dp[i][j-1]

min_path_sum.py — LC 64python

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]

    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

    return dp[m-1][n-1]

C3String DP

Compare or transform strings character by character.

Longest Common Subsequence -- "ace" vs "abcde": "" a b c d e "" [ 0 0 0 0 0 0 ] a [ 0 1 1 1 1 1 ] Arrows show transitions: c [ 0 1 1 2 2 2 ] diagonal = match (take both) e [ 0 1 1 2 2 3 ] left/up = skip one char When text1[i] == text2[j]: dp[i][j] = dp[i-1][j-1] + 1 Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

lcs.py — LC 1143python

def longest_common_subsequence(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]

Edit Distance -- three operations: Insert, Delete, Replace "" h o r s e "" [ 0 1 2 3 4 5 ] r [ 1 1 2 2 3 4 ] o [ 2 2 1 2 3 4 ] s [ 3 3 2 2 2 3 ] dp[i][j] = dp[i-1][j-1] if chars match = 1 + min(dp[i-1][j], delete dp[i][j-1], insert dp[i-1][j-1]) replace

edit_distance.py — LC 72python

def min_distance(word1, word2):
    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
    for j in range(n + 1):
        dp[0][j] = j

    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]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    return dp[m][n]

C4Knapsack DP

Coin Change (LC 322) is the unbounded knapsack: dp[i] = min coins to make amount i, trying every coin as the last one used.

step 1 / 9walkthrough — coin change, coins {1, 3, 4}, amount 6

coins {1, 3, 4}

dp[i] min coins for amount i

Cell index = amount, 0 through 6. For each amount we try every coin as the last coin used: dp[i] = min(dp[i − coin] + 1).

or use arrow keys

coin_change.py — LC 322python

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1

C5Maximum subarray — Kadane's algorithm

At each position: extend the current subarray or start fresh.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] -2 1 -3 4 -1 2 1 -5 4 curr: -2 1 -2 4 3 5 6 1 5 max: -2 1 1 4 4 5 6 6 6 Answer: 6 (subarray [4, -1, 2, 1])

max_subarray.py — LC 53python

def max_subarray(nums):
    curr_sum = max_sum = nums[0]

    for num in nums[1:]:
        curr_sum = max(num, curr_sum + num)  # Extend or restart
        max_sum = max(max_sum, curr_sum)

    return max_sum

06 space & complexity

Shrinking the table

Once the table is correct, look at what each cell actually reads. If dp[i] only touches the last one or two entries, the whole array collapses to two variables.

Pattern	Before	After
dp[i] depends on i-1	O(n)	O(1) two vars
dp[i] depends on i-1, i-2	O(n)	O(1) two vars
dp[i][j] depends on row i-1 only	O(m·n)	O(n) single row
dp[i][j] depends on rows i-1 and i-2	O(m·n)	O(2n) two rows

Complexity reference

Problem	Time	Space
Climbing Stairs	O(n)	O(1)
House Robber	O(n)	O(1)
Coin Change	O(n·m)	O(n)
Longest Common Subsequence	O(m·n)	O(m·n)
Edit Distance	O(m·n)	O(m·n)
Unique Paths	O(m·n)	O(n)
Maximum Subarray (Kadane)	O(n)	O(1)
0/1 Knapsack	O(n·W)	O(W)
Longest Increasing Subsequence	O(n log n)	O(n)

07 common mistakes

Where DP goes wrong

Mistake 1 — wrong base case

Forgetting dp[0] or initializing it with the wrong value. The whole table inherits the error.

Mistake 2 — off-by-one in table dimensions

You need dp[n+1], not dp[n], when the table is 1-indexed ("first i elements").

Mistake 3 — wrong iteration order

Bottom-up 0/1 knapsack must iterate capacity in reverse; unbounded knapsack iterates forward. Swapping them silently counts items twice (or never).

Mistake 4 — ignoring the empty string / sequence

2-D string DP needs the dp[0][j] and dp[i][0] rows — the "empty prefix" cases carry the base values.

Mistake 5 — forgetting impossible cases

Coin change can be unmakeable. Return −1 or check for the infinity sentinel before returning the table value.

Mistake 6 — unhashable memo keys

Memoization keys must be hashable — use tuple keys, not list.

08 0/1 knapsack

The subset-sum shape

Coin Change (LC 322 / 518) lets you spend the same coin as many times as you like — that is the unbounded knapsack. A second family hands you each item at most once and asks: is there a subset of these numbers that sums to exactly T? That is the 0/1 knapsack, and it is the entire trick behind LC 416 and LC 494. Once you see the shape, both become the same eight lines.

The state

reachable[s] means "using only the items processed so far, can I hit the sum s?" The base case is reachable[0] = True — the empty subset always sums to zero. Each new item asks, for every sum s: could I have reached s - item before this item existed? If yes, s is now reachable too.

nums = [1, 5, 11, 5] total = 22 target = 22 // 2 = 11 sum: 0 1 2 3 4 5 6 7 8 9 10 11 start T . . . . . . . . . . . after 1 T T . . . . . . . . . . after 5 T T . . . T T . . . . . after 11 T T . . . T T . . . . T after 5 T T . . . T T . . . T T reachable[11] is True -- the subset {11} sums to half the array, so [1, 5, 5] and [11] are an equal partition.

K1Subset sum — LC 416 Partition Equal Subset Sum

can_partition.py — LC 416python

def can_partition(nums):
    """True if nums can be split into two groups with equal sums."""
    total = sum(nums)

    # Two equal integer halves are impossible when the total is odd.
    if total % 2 == 1:
        return False

    target = total // 2

    # reachable[s] -- can some subset of the numbers seen so far sum to s?
    reachable = [False] * (target + 1)
    reachable[0] = True          # the empty subset always sums to 0

    for number in nums:
        # Walk DOWN so every cell we read (a smaller index) still holds the
        # value from BEFORE this number was allowed. That is what limits each
        # number to a single use.
        for current_sum in range(target, number - 1, -1):
            if reachable[current_sum - number]:
                reachable[current_sum] = True

    return reachable[target]

Why the inner loop counts down

Going upward, reachable[current_sum - number] could be a cell that this same number just wrote — so the number gets used twice. That is precisely the unbounded knapsack, which is correct for Coin Change II and wrong here. The loop direction is the difference between the two problems.

Problem	Item reuse	Loop shape
Coin Change II — LC 518	unlimited	for s in range(coin, target + 1)
Combination Sum IV — LC 377	unlimited, order counts	amount outer, items inner
Partition Equal Subset Sum — LC 416	once	for s in range(target, num - 1, -1)
Target Sum — LC 494	once	for s in range(target, num - 1, -1)

K2Counting subsets — LC 494 Target Sum

LC 494 looks like a different problem — assign a + or - to every number so the expression equals target — until you do the algebra. Let P be the sum of the numbers you make positive and N the sum of the ones you make negative:

P - N = target (the expression must equal the target) P + N = total (every number lands in exactly one group) ------------------------------- 2P = total + target P = (total + target) // 2 So: count the subsets whose sum is P. Same table, counts instead of booleans.

find_target_sum_ways.py — LC 494python

def find_target_sum_ways(nums, target):
    """Count the +/- sign assignments whose expression equals target."""
    total = sum(nums)

    # P = (total + target) // 2 has to be a whole, non-negative number.
    if abs(target) > total or (total + target) % 2 == 1:
        return 0

    subset_target = (total + target) // 2

    # ways[s] -- how many subsets of the numbers seen so far sum to s.
    ways = [0] * (subset_target + 1)
    ways[0] = 1                  # exactly one way to make 0: choose nothing

    for number in nums:
        # Same downward sweep as LC 416 -- each number contributes once.
        for current_sum in range(subset_target, number - 1, -1):
            ways[current_sum] += ways[current_sum - number]

    return ways[subset_target]

Swapping reachable[s] = True for ways[s] += ways[s - number] is the generic move from "is it possible?" to "how many ways?" — it works for every DP on this page.

Mistake — forgetting the parity and range guards

In LC 416 an odd total must return False immediately; in LC 494 an odd total + target, or abs(target) > total, must return 0. Skip these and you index a list with a fraction or a negative number.

Mistake — stopping the inner loop at 0

range(target, -1, -1) lets current_sum - number go negative, and Python happily wraps that into an index from the end of the list. Stop at number - 1 so current_sum never drops below number.

10 practice