Dynamic Programming (2D)

Grid DP, knapsack, LCS, edit distance, interval DP.

dp-2d.mdreadme

14 — Dynamic Programming (2D)

Neetcode Week 12a. 2D DP scales the 1D framework to two state variables. The classic problems are grids, knapsacks, two-string DP (LCS, edit distance), and DP on intervals.

Table of Contents

  1. When you need 2D DP
  2. Pattern: Grid DP
  3. Pattern: 0/1 Knapsack
  4. Pattern: Unbounded Knapsack
  5. Pattern: Two-string DP (LCS, Edit Distance)
  6. Pattern: Interleaving / Distinct Subsequences
  7. Pattern: Interval DP
  8. Space optimization tricks
  9. Pitfalls
  10. Practice list

1. When you need 2D DP

Use 2D DP when one variable isn't enough to describe the subproblem. Common signals:

  • Two indices into two strings (LCS, Edit Distance, Interleaving).
  • Index + remaining capacity / target (Knapsack, Target Sum, Coin Change).
  • Position on a grid (dp[r][c]).
  • Interval [i, j] (matrix chain, palindrome partitioning, burst balloons).

The general framework is the same as 13: define state, recurrence, base, iteration order. Just two indices instead of one.

2. Pattern: Grid DP

Unique Paths (Medium)

Robot starts at top-left, moves right or down. How many paths to bottom-right of m × n grid?

State: dp[r][c] = number of paths to (r, c). Recurrence: dp[r][c] = dp[r-1][c] + dp[r][c-1]. Base: dp[0][c] = dp[r][0] = 1.

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
    return dp[m-1][n-1]

Trace for 3×3:

1 1 1
1 2 3
1 3 6      ← 6 paths

Minimum Path Sum (Medium)

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    for r in range(m):
        for c in range(n):
            if r == 0 and c == 0: continue
            elif r == 0: grid[r][c] += grid[r][c-1]
            elif c == 0: grid[r][c] += grid[r-1][c]
            else: grid[r][c] += min(grid[r-1][c], grid[r][c-1])
    return grid[m-1][n-1]

In-place mutation saves memory. State your willingness to modify input.

Dungeon Game (Hard) — work backwards

Knight at top-left, princess at bottom-right. Cells damage or heal. Find minimum starting health to keep HP ≥ 1.

Iterate from bottom-right backward. dp[r][c] = min health needed entering cell (r, c).

def calculate_minimum_hp(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
    dp[m][n-1] = dp[m-1][n] = 1                          # exits
    for r in range(m-1, -1, -1):
        for c in range(n-1, -1, -1):
            need = min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]
            dp[r][c] = max(1, need)
    return dp[0][0]

The "must work backwards" insight is what makes this Hard.

3. Pattern: 0/1 Knapsack

n items, each with weight wi and value vi. Knapsack capacity W. Maximize total value with sum of weights ≤ W. Each item used 0 or 1 times.

2D form

State: dp[i][w] = max value using first i items with capacity w. Recurrence:

  • Skip item i: dp[i-1][w]
  • Take item i (if w ≥ wi): dp[i-1][w - wi] + vi
  • Take max.
def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i-1], values[i-1]
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]                        # skip
            if w >= wi:
                dp[i][w] = max(dp[i][w], dp[i-1][w - wi] + vi)
    return dp[n][W]

1D space-optimized form

Since each dp[i][w] depends only on dp[i-1][...], we can collapse to 1D — but iterate w backwards to avoid using the same item twice.

def knapsack_01_1d(weights, values, W):
    dp = [0] * (W + 1)
    for wi, vi in zip(weights, values):
        for w in range(W, wi - 1, -1):                   # backward!
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return dp[W]

Partition Equal Subset Sum — already in 13, this is the decision version of 0/1 knapsack.

Target Sum (Medium)

Assign + or - to each number to make total = target. Number of ways?

Reformulate: let P = sum of + group, N = sum of - group. Then P - N = target, P + N = total_sum. So P = (total + target) / 2. Now: count subsets summing to P.

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (total + target) % 2 or abs(target) > total:
        return 0
    P = (total + target) // 2
    dp = [0] * (P + 1)
    dp[0] = 1
    for num in nums:
        for s in range(P, num - 1, -1):
            dp[s] += dp[s - num]
    return dp[P]

This is "subset sum count" — same template as Coin Change II in 1D, but with backward iteration for 0/1.

4. Pattern: Unbounded Knapsack

Same as 0/1 but each item can be used unlimited times.

Difference in code: iterate w forward (so re-using the same item is OK).

def knapsack_unbounded(weights, values, W):
    dp = [0] * (W + 1)
    for wi, vi in zip(weights, values):
        for w in range(wi, W + 1):                       # forward
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return dp[W]

Coin Change (already in 13) is unbounded knapsack.

Coin Change II (number of ways) — already in 13. Note loop order matters: outer = coins, inner = amount → distinct combinations (no double counting).

5. Pattern: Two-string DP

Longest Common Subsequence (Medium)

LCS of "abcde" and "ace" = "ace" (length 3).

State: dp[i][j] = LCS of s1[:i] and s2[:j]. Recurrence:

  • If s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1].
  • Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Trace s1="abc", s2="ac":

        ""  a   c
   ""    0  0   0
    a    0  1   1
    b    0  1   1
    c    0  1   2

Answer: 2 ("ac")

Edit Distance (Hard)

Min ops (insert, delete, replace) to convert s1 to s2.

State: dp[i][j] = min ops to convert s1[:i] to s2[:j]. Recurrence:

  • If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1].
  • Else: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) (replace, insert, delete).

Base: dp[0][j] = j, dp[i][0] = i.

def min_distance(s1, s2):
    m, n = len(s1), len(s2)
    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 s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])
    return dp[m][n]

This is the classic 2D DP. Memorize the structure.

Interpretation of the three operations

              s1[:i]                 s1[:i]                  s1[:i]
              ↓ replace              ↓ delete                ↓ insert
   ↓ s1[:i-1]                  ↓ s1[:i-1]              ↓ s1[:i]
              s2[:j-1]              s2[:j]                  s2[:j-1]
              s2[:j]                s2[:j]                  s2[:j]
              
   dp[i-1][j-1] + 1                 dp[i-1][j] + 1         dp[i][j-1] + 1
   (replace s1[i-1] with s2[j-1])   (delete s1[i-1])       (insert s2[j-1])

6. Pattern: Interleaving / Distinct Subsequences

Interleaving String (Medium)

Is s3 an interleaving of s1 and s2?

State: dp[i][j] = can s3[:i+j] be formed from s1[:i] and s2[:j]? Recurrence:

  • From s1: dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i+j-1].
  • From s2: dp[i][j] = dp[i][j-1] and s2[j-1] == s3[i+j-1].
  • OR them.
def is_interleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m + n != len(s3): return False
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 and j == 0: continue
            from_s1 = i > 0 and dp[i-1][j] and s1[i-1] == s3[i+j-1]
            from_s2 = j > 0 and dp[i][j-1] and s2[j-1] == s3[i+j-1]
            dp[i][j] = from_s1 or from_s2
    return dp[m][n]

Distinct Subsequences (Hard)

Count distinct subsequences of s that equal t.

State: dp[i][j] = ways s[:i] contains t[:j] as subseq. Recurrence:

  • Skip s[i-1]: dp[i-1][j].
  • Use s[i-1] to match t[j-1] (if equal): + dp[i-1][j-1].
def num_distinct(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = 1
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j]
            if s[i-1] == t[j-1]:
                dp[i][j] += dp[i-1][j-1]
    return dp[m][n]

7. Pattern: Interval DP

State is dp[i][j] for an interval [i, j]. Process in order of increasing length.

Burst Balloons (Hard)

Pop balloons one at a time. When popping balloon i, get nums[i-1] * nums[i] * nums[i+1] coins (treating boundaries as 1). Maximum coins?

Re-frame: instead of "which one to pop first," think "which one is popped last in interval (i, j)."

State: dp[i][j] = max coins from popping all balloons in (i, j) exclusive. Recurrence: for each k in (i, j) as last-popped:

dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])

def max_coins(nums):
    nums = [1] + nums + [1]                              # boundary
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n):                            # interval length
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j],
                               dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
    
    return dp[0][n-1]

The "iterate by interval length" pattern is critical — when computing dp[i][j], the smaller intervals it depends on are already computed.

This is one of the hardest "must-know" DPs.

Matrix Chain Multiplication (Hard, classic)

Same template — interval DP with dp[i][j] = min cost to multiply matrices i..j.

8. Space optimization

When dp[i][...] depends only on dp[i-1][...], you can use two rolling 1D arrays — or just one if you iterate carefully.

Knapsack 1D (already shown above)

LCS rolling

def lcs_rolling(s1, s2):
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    cur = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                cur[j] = 1 + prev[j-1]
            else:
                cur[j] = max(prev[j], cur[j-1])
        prev, cur = cur, [0] * (n + 1)
    return prev[n]

When NOT to space-optimize in interview

If you're tight on time or worried about bugs, leave it 2D. State that you could optimize it. Most interviewers prefer a working O(m·n) space solution over a buggy O(n) one.

9. Pitfalls

Wrong dimension for dp

Common: dp = [[0]*n]*m — this creates m references to the same row. Use [[0]*n for _ in range(m)].

Missing base case for empty strings

dp[0][j] and dp[i][0] — what do they mean? For LCS, both 0 (empty string contains no subseq except empty). For Edit Distance, dp[0][j] = j and dp[i][0] = i.

Iteration order in 2D

You must iterate so dependencies are computed first. Usually rows then cols, but for backward DPs (Dungeon), reverse. For interval DP, iterate by length.

Forgetting boundaries in interval DP

nums = [1] + nums + [1] for Burst Balloons — without it, the recurrence references out-of-bounds indices.

Confusing 0/1 vs unbounded

  • 0/1: each item used at most once → iterate w backwards in 1D.
  • Unbounded: each item used unlimited times → iterate w forward in 1D.

Single most common bug.

Python 2D list slicing

dp[1:][:] makes a shallow copy. For 2D you need [row[:] for row in dp] or copy.deepcopy(dp).

10. Practice list

#ProblemPatternDifficulty
62Unique PathsGridMedium
64Minimum Path SumGridMedium
1143Longest Common SubsequenceTwo-stringMedium
72Edit DistanceTwo-stringHard
97Interleaving StringTwo-stringMedium
115Distinct SubsequencesTwo-stringHard
309Best Time Buy/Sell with CooldownState machineMedium
518Coin Change IIUnbounded knapsackMedium
494Target Sum0/1 knapsackMedium
416Partition Equal Subset Sum0/1 knapsackMedium
312Burst BalloonsInterval DPHard
174Dungeon GameReverse grid DPHard

TL;DR ✅

  • 2D DP when state needs two variables: index pair, item + capacity, position on grid, or interval.
  • 0/1 knapsack: iterate weight backward in 1D. Unbounded: iterate forward.
  • LCS / Edit Distance are the canonical two-string DPs. Memorize the structures.
  • Interval DP iterates by interval length so dependencies are ready.
  • Space optimize to 1D rolling when only previous row matters — but don't sacrifice correctness for it.
  • Burst Balloons = think last one to pop in an interval. Lifts you out of "which first" trap.

Next: 15-greedy-intervals.md.

External resources

problems/7 entries
●main
UTF-8·typescript