2-D DP extends 1-D DP: instead of a single index dp[i], the state is a whole
table dp[i][j] indexed by two things at once – typically two positions in
two strings, or a row and column in a grid. The answer for cell (i, j) is built
from already-computed neighbours: the cell above dp[i-1][j], the cell to the
left dp[i][j-1], and very often the diagonal dp[i-1][j-1]. You fill
the table row by row (or length by length) until the bottom-right cell holds the
final answer.
The hallmark: the problem’s state needs two “pointers” to describe. The moment you catch yourself saying “the answer depends on where I am in X and where I am in Y”, you are in 2-D DP territory.
Scan the statement for any of these:
| Trigger signal | Likely sub-pattern |
|---|---|
| “robot moves only right/down”, “number of ways to reach” | Grid-path DP |
| “two strings”, “longest common subsequence”, “common to both” | LCS-style DP |
| “convert word1 to word2”, “edit distance”, “insert/delete/replace” | Edit-distance DP |
| “subset that sums to target”, “0/1 knapsack”, “partition into equal” | Knapsack DP (0/1) |
| “number of combinations to make amount”, “unlimited coins” | Knapsack DP (unbounded) |
| “is s[i..j] a palindrome”, “count palindromic substrings” | Interval DP (2-D on i, j) |
Three things define every 2-D DP. Decide them in this order and the code almost writes itself.
i and j represent? Row/column of a grid; a prefix of
string A / a prefix of string B; the start and end of a substring; an item
index / a running sum. Write the definition as a sentence before any code.dp[i][j] computed from its neighbours? Almost always a
combination of dp[i-1][j] (above), dp[i][j-1] (left), and dp[i-1][j-1]
(diagonal). This is the heart of the problem.dp[0][*] and the left column dp[*][0] are filled
first, before the main loops, because they have no “above” or “left” to
read from. Getting these wrong is the number-one source of bugs.function solveTwoD(input):
let m = number of rows, n = number of columns
create a dp table of size (m+1) by (n+1) # +1 reserves a "zero" row and column
fill the base row dp[0][*] and base column dp[*][0]
for i from 1 to m:
for j from 1 to n:
dp[i][j] = combine(
dp[i-1][j], # answer without the current row's element
dp[i][j-1], # answer without the current column's element
dp[i-1][j-1] # answer without either
)
return dp[m][n]
The (m+1) x (n+1) sizing with a sentinel row/column of zeros is the single most
useful convention: it removes every special case for the first real row and
column, because they always have a valid “above” (the sentinel row) and “left”
(the sentinel column) to read. Edit Distance, LCS, and the knapsack family all
benefit.
For pure grid problems where cell (0,0) has its own value rather than
representing an “empty prefix”, you size the table m x n and fill row 0 and
column 0 explicitly before the loops – see Unique Paths and Minimum Path Sum.
Ask one question: how many independent positions do I need to describe a sub-problem?
If you can phrase the sub-problem as “the answer for the first i of X and
the first j of Y”, it is 2-D.
State = a grid cell. Movement is restricted to right and down, so each cell’s answer combines only the cell above and the cell to the left. Base = the top row and the left column, each of which has exactly one way to be reached.
State = a prefix of string A paired with a prefix of string B. When the two
current characters match, extend the diagonal: dp[i-1][j-1] + 1. When they
do not, carry forward the best of the two neighbours: max(dp[i-1][j],
dp[i][j-1]). Base = a row and column of zeros (the empty prefix matches nothing).
State = prefixes of two strings. Three operations map to three neighbours:
dp[i][j-1] + 1
(we consumed a char of word2 but not word1).dp[i-1][j] + 1 (we consumed a char of
word1 but not word2).dp[i-1][j-1] + 1 (we consumed one char of each).When the two current characters already match, the cost is dp[i-1][j-1] – the
operation is free. Base: row 0 = j (insert j chars into an empty string),
column 0 = i (delete i chars to reach an empty string).
State = (item index, remaining capacity). For each item you choose: include it or skip it. The two flavours differ only in loop direction:
Read them in this order – grid first (simplest recurrence), then two-string DP, then interval DP, then the two knapsack variants.
| # | Problem | Difficulty | Teaser |
|---|---|---|---|
| 0062 | Unique Paths | Medium | The simplest grid DP: dp[i][j] = dp[i-1][j] + dp[i][j-1]. |
| 0064 | Minimum Path Sum | Medium | Grid DP with cell costs: add the cheaper of above / left. |
| 1143 | Longest Common Subsequence | Medium | Textbook LCS: diagonal +1 on a match, else max of the two neighbours. |
| 0072 | Edit Distance | Medium | The classic: insert / delete / replace map to three neighbours. |
| 0647 | Palindromic Substrings | Medium | Interval DP: dp[i][j] depends on dp[i+1][j-1] – fill by length. |
| 0518 | Coin Change II | Medium | Combination count: loop order decides combinations vs permutations. |
| 0416 | Partition Equal Subset Sum | Medium | 0/1 knapsack in disguise: can a subset hit sum / 2? |
(m+1) x (n+1) convention the sentinel row and column are zeros; under the
grid convention they are running sums (Minimum Path Sum) or all-1s (Unique
Paths).(len1+1) x (len2+1) table uses indices
0..len1 and 0..len2, so the recurrence reads text.charAt(i-1) and
text.charAt(j-1). Mixing up i with i-1 when indexing the original string
is the single most common bug in this pattern.i and j. By convention i indexes rows (outer loop) and j
indexes columns (inner loop). Writing dp[j][i] or text2.charAt(i-1)
compiles and runs but yields wrong answers. Pick a convention and keep it for
the whole solution.dp[i+1][j-1] (Palindromic Substrings) cannot be filled top-down row by row,
because i+1 sits below i. Either fill by substring length, or iterate
i descending and j ascending.dp[i-1][j-1] is overwritten
before it is read in the next column. Carry a prev variable that snapshots
the old dp[j-1] before the update.Five questions ramping from recall to design. Try each before revealing.
Q1 (recall). In one sentence, what makes a problem 2-D DP rather than 1-D DP?
Q2 (pattern recognition). A new problem: “a robot walks a grid of coins moving only right/down and wants to MAXIMISE the coins collected.” Which sub-pattern fits?
max instead of min)Q3 (pattern recognition). A new problem: “choose items, each usable at most once, so their weights sum exactly to W.” Which sub-pattern and, in 1-D form, which inner-loop direction?
Q4 (apply). For Edit Distance with word1 = "ab", word2 = "ab", what is dp[2][2]?
Q5 (design). Sketch (in words, not code) a 2-D DP for “count the number of subsequences of string s that equal string t” – how would you define dp[i][j] and the recurrence?
Next problem: 0062 - Unique Paths.