2D Dynamic Programming
Overview
2D Dynamic Programming applies the exact same caching concept to problems where the state depends on Two changing variables. Because there are two dimensions to track, the cache requires a 2D Array (a Matrix).
A classic example is finding the number of 'Unique Paths' a robot can take on a Grid from the top-left to the bottom-right, only being allowed to move down or right. The robot's state is defined by its Row (y) and its Column (x).
The mathematical beauty of this problem is that the number of unique ways to reach cell (y, x) is simply the sum of the ways to reach the cell directly above it PLUS the ways to reach the cell directly to its left.
By storing these results in a dp[row][col] matrix, an exponential recursive maze-solving problem becomes a lightning-fast, simple nested loop.
Syntax
public class DP2D {
public int uniquePaths(int rows, int cols) {
// Create 2D cache
int[][] dp = new int[rows][cols];
// Base case: There is only 1 way to travel along the top edge or left edge
// (because you can only move in a straight line to reach them)
for (int i = 0; i < rows; i++) dp[i][0] = 1;
for (int j = 0; j < cols; j++) dp[0][j] = 1;
// Fill the grid based on previous results
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
// The number of ways to reach THIS cell is the sum of ways to reach
// the cell strictly above it AND strictly to the left of it.
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// The bottom-right cell contains the final accumulated answer
return dp[rows - 1][cols - 1];
}
}Common Pitfalls
- Initializing boundaries incorrectly. If you forget to populate the 0th row and 0th column, your algorithm will just sum zeros infinitely.
- Extremely high memory consumption. A 2D array of size 10,000 x 10,000 consumes 400MB of RAM. 2D DP algorithms are notorious memory hogs if not aggressively optimized.
- Index Out of Bounds. Always double check your
i-1andj-1logic. Your nested loops must start at index 1 to avoid querying negative indices.
Interview Questions
Yes, incredibly well. In the Unique Paths problem, calculating the current row only requires data from the current row and the previous row. You can completely discard all older rows. This drops the Space Complexity from O(Rows * Cols) down to just O(Cols) by using a 1D array.
It is one of the most famous 2D DP problems. Given two strings, you find the longest sequence of characters that appear in both in the same order. It uses a 2D matrix where rows represent string A and columns represent string B.
Real-World Example
Levenshtein Distance for Spell Checking and DNA sequencing. When you misspell 'algorhythm', how does Google know to suggest 'algorithm'? It uses a 2D DP algorithm (Edit Distance) that compares two strings character by character in a matrix, calculating the minimum number of insertions, deletions, or substitutions required to transform one string into the other.
public class SpellChecker {
// 2D DP to calculate Minimum Edit Distance
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // Characters match, no cost
} else {
// Min of Replace, Delete, or Insert
dp[i][j] = Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
}
return dp[m][n];
}
}Check Your Knowledge
Test your understanding of 2D Dynamic Programming with these quick questions.