Topic 74 of 78
2D Dynamic Programming
Overview
2D Dynamic Programming is used when the problem's state depends on two varying parameters, requiring a 2D matrix (grid) to store the cached answers. It is famously used for Grid Traversals (like finding the unique paths from the top-left to the bottom-right of a grid) and String matching problems (like the Longest Common Subsequence between two words).
Syntax
The state of any cell depends on two coordinates (row and col). The 2D array maps perfectly to this logic.
Unique Paths in a Grid
java
// Find number of ways to reach bottom-right corner, moving only Right or Down
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// Fill the first row and first column with 1s (only one way to move straight)
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
// Calculate the inner cells
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// Ways to reach cell = ways from ABOVE + ways from LEFT
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}Common Pitfalls
- Off-by-one errors when defining the size of the 2D array. Sometimes you need `new int[m+1][n+1]` to act as a buffer for the base cases.
Interview Tips
- The longest common subsequence (LCS) and Edit Distance are classic 2D DP problems that every engineer should memorize.
Real-World Example
Diff tools (like Git Diff) use the Longest Common Subsequence (a 2D DP algorithm) to calculate exactly which lines were added or removed between two files.
example
java
// Git diff compares two files line by line using an optimized 2D DP LCS approach.