PATTERN 17 OF 22

Dynamic Programming (2D)

Extend DP to two-dimensional state spaces: grid path counting, two-string comparison (LCS, edit distance), and 2D knapsack variants. Master the dp[i][j] table, understand how to set up base cases for rows and columns, and optimize space with rolling arrays.

Time: O(m · n) for grid and two-string DP, O(n · W) for knapsack

Space: O(m · n) for full table, O(n) with space optimization

Learn & Reference

Understanding the Pattern

Dynamic Programming (2D) Pattern

2D Dynamic Programming extends the 1D concepts you already know to problems with two-dimensional state. Instead of dp[i], you now fill a 2D table dp[i][j] where each cell depends on its neighbors.

Grid DP (Unique Paths):        Two-String DP (LCS):

  1  1  1  1                    ""  a  c  e
  1  2  3  4                ""   0  0  0  0
  1  3  6  10               a    0  1  1  1
                            b    0  1  1  1
dp[i][j] = dp[i-1][j]      c    0  1  2  2
          + dp[i][j-1]      d    0  1  2  2
                            e    0  1  2  3

Three Major Archetypes

1. Grid DP

The state is a position in a grid. You can typically only move right or down (or from top-left neighbors).

dp[i][j] = f(dp[i-1][j], dp[i][j-1])

Examples: Unique Paths, Minimum Path Sum, Dungeon Game

Base cases: First row and first column are filled directly (only one way to reach them).

2. Two-String DP

The state represents prefixes of two strings: dp[i][j] = answer for s1[0..i) and s2[0..j).

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1       # characters match
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one character

Examples: Longest Common Subsequence, Edit Distance, Wildcard Matching

Base cases: dp[0][j] and dp[i][0] represent comparing with an empty string.

3. 2D Knapsack

One dimension is the item index, the other is the capacity/target. Often space-optimized to 1D.

Full 2D:  dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i]]
1D opt:   dp[j] += dp[j - coin]   (iterate right for unbounded)
          dp[j] += dp[j - num]    (iterate left for 0/1)

Examples: Coin Change II, Target Sum, 0/1 Knapsack, Subset Sum

Base case: dp[0] = 1 (one way to make amount 0: use nothing).

Space Optimization

When dp[i][j] only depends on the current row and the row above, you can use a rolling array (two 1D arrays) or even a single 1D array updated carefully:

# Grid DP: single row, update left-to-right
dp = [1] * n
for i in range(1, m):
    for j in range(1, n):
        dp[j] += dp[j-1]

# 0/1 Knapsack: single row, update RIGHT-TO-LEFT (preserve previous row values)
for num in nums:
    for j in range(target, num - 1, -1):
        dp[j] += dp[j - num]

# Unbounded Knapsack: single row, update LEFT-TO-RIGHT (allow reuse)
for coin in coins:
    for j in range(coin, amount + 1):
        dp[j] += dp[j - coin]

DFS + Memoization on Grids

Some 2D DP problems are easier solved top-down with DFS + memoization rather than bottom-up tabulation. This is especially true for grid problems where the dependency direction varies (e.g., longest increasing path can go in any of 4 directions).

memo = {}
def dfs(i, j):
    if (i, j) in memo: return memo[(i, j)]
    result = 1  # at least the cell itself
    for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
        ni, nj = i+di, j+dj
        if in_bounds(ni, nj) and grid[ni][nj] > grid[i][j]:
            result = max(result, 1 + dfs(ni, nj))
    memo[(i, j)] = result
    return result

Common Mistakes

Wrong table dimensions — For two-string DP, the table should be (m+1) x (n+1) to include the empty string. Using m x n causes off-by-one errors and missing base cases.
Forgetting base case initialization — The first row and first column of the DP table need explicit initialization. For grid DP, the first row/column is often all 1s. For edit distance, dp[i][0] = i and dp[0][j] = j.
String indexing vs DP indexing — When dp[i][j] represents prefixes of length i and j, the corresponding string characters are s1[i-1] and s2[j-1], not s1[i] and s2[j]. This off-by-one is the #1 bug in two-string DP.
Wrong iteration direction for knapsack — For 0/1 knapsack (each item used once), iterate capacity right-to-left. For unbounded knapsack (items reusable), iterate left-to-right. Reversing these produces wrong answers.
Not handling edge cases — Empty strings, single-cell grids, zero target amounts, and impossible cases (odd target sum) all need special handling before the main DP loop.

When to Use

The problem involves a **grid** and asks for paths, minimum cost, or counting routes

You need to compare **two strings** (LCS, edit distance, wildcard matching, interleaving)

The problem is a **knapsack variant** with items and capacity (coin change counting, target sum, subset sum)

The state naturally has **two dimensions**: two indices, row+column, item+capacity

You solved the 1D version and now need to generalize to 2D

Keywords: grid, paths, LCS, edit distance, knapsack, subset sum, number of ways

Template

1# --- Grid DP Template ---
2def solve_grid(grid):
3    m, n = len(grid), len(grid[0])
4    dp = [[0] * n for _ in range(m)]
5
6    # Base cases: first row and first column
7    dp[0][0] = grid[0][0]
8    for j in range(1, n): dp[0][j] = f(dp[0][j-1], grid[0][j])
9    for i in range(1, m): dp[i][0] = f(dp[i-1][0], grid[i][0])
10
11    # Fill table
12    for i in range(1, m):
13        for j in range(1, n):
14            dp[i][j] = f(dp[i-1][j], dp[i][j-1], grid[i][j])
15
16    return dp[m-1][n-1]
17
18# --- Two-String DP Template ---
19def solve_strings(s1, s2):
20    m, n = len(s1), len(s2)
21    dp = [[0] * (n + 1) for _ in range(m + 1)]
22
23    # Base cases: dp[i][0] and dp[0][j]
24
25    for i in range(1, m + 1):
26        for j in range(1, n + 1):
27            if s1[i-1] == s2[j-1]:
28                dp[i][j] = dp[i-1][j-1] + 1  # match
29            else:
30                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # no match
31
32    return dp[m][n]

{ }

Syntax Reference

1# --- 2D Array Initialization ---
2dp = [[0] * (n + 1) for _ in range(m + 1)]  # (m+1) x (n+1) table
3dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]  # For minimization
4dp = [[False] * (n + 1) for _ in range(m + 1)]  # For boolean DP
5
6# WARNING: dp = [[0] * n] * m  ← WRONG! All rows share same list
7
8# --- Nested Iteration ---
9for i in range(1, m + 1):
10    for j in range(1, n + 1):
11        dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
12
13# --- Space Optimization (rolling 1D array) ---
14dp = [0] * (n + 1)
15for i in range(1, m + 1):
16    prev = dp[0]  # save dp[i-1][j-1]
17    for j in range(1, n + 1):
18        temp = dp[j]
19        dp[j] = f(dp[j], dp[j-1], prev)  # dp[j] = above, dp[j-1] = left
20        prev = temp
21
22# --- DFS + Memoization (grid) ---
23from functools import lru_cache
24
25@lru_cache(maxsize=None)
26def dfs(i, j):
27    # base case + recurse on neighbors
28    pass

📋

Common Recipes

1# Recipe 1: Unique Paths (Grid DP, space-optimized)
2def unique_paths(m, n):
3    dp = [1] * n
4    for i in range(1, m):
5        for j in range(1, n):
6            dp[j] += dp[j - 1]
7    return dp[n - 1]
8
9# Recipe 2: Longest Common Subsequence (Two-String DP)
10def longest_common_subsequence(text1, text2):
11    m, n = len(text1), len(text2)
12    dp = [[0] * (n + 1) for _ in range(m + 1)]
13    for i in range(1, m + 1):
14        for j in range(1, n + 1):
15            if text1[i - 1] == text2[j - 1]:
16                dp[i][j] = dp[i - 1][j - 1] + 1
17            else:
18                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
19    return dp[m][n]
20
21# Recipe 3: Edit Distance (Two-String DP)
22def min_distance(word1, word2):
23    m, n = len(word1), len(word2)
24    dp = [[0] * (n + 1) for _ in range(m + 1)]
25    for i in range(m + 1): dp[i][0] = i
26    for j in range(n + 1): dp[0][j] = j
27    for i in range(1, m + 1):
28        for j in range(1, n + 1):
29            if word1[i - 1] == word2[j - 1]:
30                dp[i][j] = dp[i - 1][j - 1]
31            else:
32                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
33    return dp[m][n]
34
35# Recipe 4: 0/1 Knapsack Counting (space-optimized)
36def knapsack_count(nums, target):
37    dp = [0] * (target + 1)
38    dp[0] = 1
39    for num in nums:
40        for j in range(target, num - 1, -1):  # RIGHT-TO-LEFT for 0/1
41            dp[j] += dp[j - num]
42    return dp[target]

O(n)

Complexity

Archetype	Time	Space	Example
Grid DP	O(m · n)	O(n)*	Unique Paths, Min Path Sum
Two-String DP	O(m · n)	O(m · n)	LCS, Edit Distance
2D Knapsack	O(n · W)	O(W)*	Coin Change II, Target Sum
Grid DFS + Memo	O(m · n)	O(m · n)	Longest Increasing Path

Watch Out

✗Wrong table dimensions — For two-string DP, the table should be `(m+1) x (n+1)` to include the empty string. Using `m x n` causes off-by-one errors and missing base cases.
✗Forgetting base case initialization — The first row and first column of the DP table need explicit initialization. For grid DP, the first row/column is often all 1s. For edit distance, `dp[i][0] = i` and `dp[0][j] = j`.
✗String indexing vs DP indexing — When `dp[i][j]` represents prefixes of length `i` and `j`, the corresponding string characters are `s1[i-1]` and `s2[j-1]`, not `s1[i]` and `s2[j]`. This off-by-one is the #1 bug in two-string DP.
✗Wrong iteration direction for knapsack — For 0/1 knapsack (each item used once), iterate capacity right-to-left. For unbounded knapsack (items reusable), iterate left-to-right. Reversing these produces wrong answers.
✗Not handling edge cases — Empty strings, single-cell grids, zero target amounts, and impossible cases (odd target sum) all need special handling before the main DP loop.

PRACTICE PROBLEMS

Intervals

Advanced Graphs