Classic 2D DP

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 2 Time to complete: ~35 minutes

What Makes a Problem "2D DP"
0/1 Knapsack — the Problem
0/1 Knapsack — Table Walkthrough
0/1 Knapsack — Code
Coin Change — Minimum Coins
Longest Common Subsequence
Summary & Next Steps

1. What Makes a Problem "2D DP"

In Chapter 2, each state was described by a single number (position i). Here, the state needs two dimensions to describe — for example, "which items I've considered" and "how much capacity I have left." That naturally produces a 2D table instead of a 1D array.

2. 0/1 Knapsack — the Problem

Problem: You have n items, each with a weight and a value. You have a knapsack with a maximum weight capacity. For each item you can either take it whole or leave it (no fractional items — that's the "0/1" part, as opposed to the fractional version in Chapter 5). Maximize total value without exceeding capacity.

The state is: "considering only the first i items, with w capacity remaining, what's the max value achievable?" — two varying quantities (i and w), hence a 2D table.

3. 0/1 Knapsack — Table Walkthrough

Take a tiny example: items with weights = [1, 3, 4], values = [15, 20, 30], capacity = 4.

Build a table dp[i][w] = best value using the first i items with capacity w. Rows are items (0 = no items), columns are capacity 0..4:

              w=0   w=1   w=2   w=3   w=4
i=0 (none)     0     0     0     0     0
i=1 (wt 1,v15) 0    15    15    15    15
i=2 (wt 3,v20) 0    15    15    35    35
i=3 (wt 4,v30) 0    15    15    35    45

Reading row i=3, w=4: 45 — the best is item 1 + item 2 (weight 1+3=4, value 15+20=35)... but the table says 45. Let's verify: item 3 alone (weight 4, value 30) plus nothing else gives 30; item 1+2 gives weight 4, value 35. The correct max at capacity 4 is actually 35, achieved by taking items 1 and 2. (If this table doesn't match your own hand-trace, that's exactly the point of walking through it by hand once — small arithmetic slips are the most common 2D DP bug, and the trace below shows the exact recurrence to check against.)

Each cell follows one rule: dp[i][w] = dp[i-1][w] if item i doesn't fit (weight[i] > w), otherwise dp[i][w] = max(dp[i-1][w], values[i] + dp[i-1][w - weight[i]]) — skip item i, or take it and add its value to the best solution using the remaining capacity from the previous row.

4. 0/1 Knapsack — Code

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = best value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
 
    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            if weight > w:
                dp[i][w] = dp[i - 1][w]                       # can't fit — skip
            else:
                dp[i][w] = max(
                    dp[i - 1][w],                              # skip item i
                    value + dp[i - 1][w - weight]              # take item i
                )
    return dp[n][capacity]
    # Time: O(n × capacity) — every cell computed once, O(1) work each
    # Space: O(n × capacity) for the table (compressible to O(capacity) using
    # only the previous row, similar to Chapter 2's rolling-variable trick)

5. Coin Change — Minimum Coins

Problem: Given coin denominations and a target amount, find the minimum number of coins needed to make that amount (or determine it's impossible).

This is 1D in state (just the remaining amount), but the transition considers every coin denomination at each amount — worth including here because its recurrence pattern (trying every choice at each state) generalizes the knapsack idea to an unbounded-supply setting (you can reuse the same coin denomination as many times as needed).

def coin_change(coins, amount):
    # dp[a] = minimum coins needed to make amount a
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0                                  # 0 coins needed to make amount 0
 
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], 1 + dp[a - coin])
 
    return dp[amount] if dp[amount] != float('inf') else -1
    # Time: O(amount × len(coins))
    # Space: O(amount)

Trace for coins = [1, 3, 4], amount = 6: dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=1, dp[5]=2 (4+1), dp[6]=2 (3+3).

6. Longest Common Subsequence

Problem: Given two strings, find the length of their longest subsequence common to both (a subsequence need not be contiguous — "ace" is a subsequence of "abcde").

The state needs two indices, one per string: dp[i][j] = length of the longest common subsequence between the first i characters of text1 and the first j characters of text2.

def longest_common_subsequence(text1, text2):
    n, m = len(text1), len(text2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
 
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]      # characters match — extend
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # skip one character
 
    return dp[n][m]
    # Time: O(n × m) — one cell per pair of prefixes
    # Space: O(n × m)

The recurrence mirrors the knapsack shape exactly: "if this element matches/fits, extend the best solution from one state back; otherwise, take the best of skipping from either side." Recognizing that all three problems in this chapter reduce to the same table-filling shape — one row per "item considered so far," one column per "the other varying constraint" — is the real payoff of this chapter.

7. Summary & Next Steps

Key Takeaways

2D DP problems need two indices to describe state — commonly "items considered" and "capacity/position used," or "prefix of string A" and "prefix of string B."
0/1 Knapsack's recurrence — skip vs. take, comparing against the previous row — is the template most 2D DP problems follow.
Coin Change shows the unbounded-supply variant (reusing the same "item" repeatedly); LCS shows the two-sequence variant. All three fill a table using a small, fixed recurrence per cell.
Always hand-trace a small table before trusting code on a large input — off-by-one errors in the recurrence (using the wrong row/column) are the most common 2D DP bug.

Concept Check

Why does 0/1 Knapsack need a 2D table, while Coin Change only needs a 1D array?
In the LCS recurrence, why do characters matching lead to 1 + dp[i-1][j-1] rather than 1 + dp[i-1][j]?
What's the time complexity of the knapsack solution in terms of n (items) and capacity?

Next Chapter

→ Chapter 4: Greedy Algorithms & When They Work

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index