LeetCode Solutions← Back to Patterns
Dynamic ProgrammingHard
2D DP
Two-state DP table where dp[i][j] captures two dimensions of the problem.
How it works
Two-dimensional DP uses a table where each cell dp[i][j] represents the solution to a subproblem defined by two parameters — often indices into two strings, or row/column in a grid. You fill the table in a specific order (usually top-left to bottom-right) so that when you compute dp[i][j], all dependencies (dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) are already filled. Classic problems: Edit Distance (min operations to transform s1→s2), Longest Common Subsequence (longest shared subsequence), and Unique Paths (count paths in a grid). The table itself makes the recurrence visible: draw it on paper first.
Interactive Playground
dp[i][j] = number of unique paths from (0,0) to (i,j).
Speed
When to use
- Edit distance and longest common subsequence
- Grid path counting or minimum cost
- String matching with two input strings
✅Tips
1Use a (m+1) × (n+1) table with an extra row/column for the empty string base case — avoids conditional checks.
2For LCS: dp[i][j] = dp[i-1][j-1]+1 if chars match, else max(dp[i-1][j], dp[i][j-1]).
3For Edit Distance: dp[i][j] = dp[i-1][j-1] if match, else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
4Space optimization: if dp[i][j] only depends on the previous row, use two 1D arrays (curr and prev).
❌Common Mistakes
!Forgetting to initialize the base cases (first row and first column) — these represent empty string comparisons.
!Filling the table in the wrong order — dependencies must be computed before the current cell.
!Confusing LCS with Longest Common Substring — substring requires contiguous characters (reset to 0 on mismatch).
!Not allocating the extra +1 row/column for the empty-string base case.
💡 Key Insight:Draw the table first. Fill row by row — the recurrence is visible in adjacent cells.