2D Dynamic Programming
The Intuition
Picture two words written on a whiteboard: "KITTEN" across the top and "SITTING" down the side. You draw a grid where each cell (i, j) answers a question: "What's the best answer if I only consider the first i characters of one word and the first j characters of the other?" That single question, asked for every combination of prefixes, is the heart of 2D DP.
You start filling in the grid from the top-left corner. The first row and first column are your base cases, usually straightforward. Cell (0, 0) is trivial. Then you work your way across each row, left to right, top to bottom. Each cell peeks at its neighbors: the cell directly above, the cell to the left, and the cell diagonally above-left. Those three neighbors represent your choices. For edit distance, they correspond to deleting, inserting, or replacing a character. For longest common subsequence, they represent skipping a character from one string or matching characters from both.
The beauty is that every 2D string problem follows the same skeleton. Edit distance, longest common subsequence, interleaving strings, regex matching. You set up the same grid, define the same three-neighbor dependency, and just change the rules for how you compute each cell's value. Once you internalize "two strings, one grid, three directions," a whole class of problems clicks into place.
Grid navigation problems (like counting unique paths or finding minimum path sums) use the same structure, but the two dimensions are row and column instead of two string indices. Each cell depends on the cell above and the cell to the left, because you can only move down or right. The recurrence changes, but the pattern of building answers from previously computed answers stays identical.
Longest common subsequence, edit distance, grid path counting, 0/1 knapsack, minimum path sum, regex matching, or any problem with two-dimensional subproblem structure.
- Strings are extremely long and memory is limited (optimize to 1D)
- Problem has greedy property (greedy is simpler)
- Need the actual path not just the value (requires backtracking through the DP table)
Variations:
- String DP: Compare two strings character by character (LCS, edit distance).
- Grid DP: Navigate a 2D grid (unique paths, minimum path sum).
- Knapsack DP: Select items with weight/value trade-offs.
- Space-optimized: Reduce from 2D array to two 1D arrays or a single 1D array when possible.
- 1x1 grid (single cell, trivial answer)
- Empty string for one or both inputs
- Both strings are identical
Key Points
- •State has two dimensions: dp[i][j] = optimal answer for subproblem (i, j)
- •Common patterns: grid paths, string matching, knapsack
- •Fill table row by row or diagonally depending on dependencies
- •Space optimization: if row i depends only on row i-1, use two 1D arrays
- •Base cases: first row and/or first column
Code Template
1 def longest_common_subsequence(text1, text2):
2 """Length of LCS of two strings."""
3 m, n = len(text1), len(text2)
4 dp = [[0] * (n + 1) for _ in range(m + 1)]
5
6 for i in range(1, m + 1):
7 for j in range(1, n + 1):
8 if text1[i - 1] == text2[j - 1]:
9 dp[i][j] = dp[i - 1][j - 1] + 1
10 else:
11 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
12
13 return dp[m][n]
14
15 def unique_paths(m, n):
16 """Number of unique paths in m x n grid (right/down only)."""
17 dp = [1] * n # space-optimized to 1D
18 for _ in range(1, m):
19 for j in range(1, n):
20 dp[j] += dp[j - 1]
21 return dp[n - 1]
22
23 def knapsack_01(weights, values, capacity):
24 """0/1 Knapsack: max value within capacity."""
25 n = len(weights)
26 dp = [0] * (capacity + 1)
27 for i in range(n):
28 for w in range(capacity, weights[i] - 1, -1):
29 dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
30 return dp[capacity]Common Mistakes
- Wrong direction of table filling (must respect dependencies)
- Not initializing base cases for both dimensions
- Applying space optimization when state depends on more than the previous row