Dynamic Programming (2D)
2D dynamic programming extends the 1D concept by using a two-dimensional table where each cell dp[i][j] represents the solution to a subproblem defined by two parameters. This is necessary when the state depends on two changing variables, such as two string indices, a range of elements, or grid coordinates. Classic examples include edit distance, longest common subsequence, and grid path counting.
When to Use
- →The problem involves two sequences that need to be compared or aligned
- →You need to find paths or costs in a 2D grid
- →The subproblem requires two indices to define its state (e.g., substring i..j)
- →You need to compute optimal solutions over ranges (interval DP)
Approach
Define dp[i][j] clearly. For longest common subsequence: dp[i][j] = LCS length of first i characters and first j characters. For edit distance: dp[i][j] = minimum edits to convert first i chars of word1 to first j chars of word2. For grid paths: dp[i][j] = number of paths to reach cell (i,j).
Fill the table using nested loops, typically iterating i from 0 to m and j from 0 to n. Initialize base cases (first row, first column, or diagonal). The recurrence often involves looking at dp[i-1][j], dp[i][j-1], and dp[i-1][j-1].
Space optimization: if each row only depends on the previous row, you can reduce from O(mn) to O(n) space by using two 1D arrays (current and previous row) or even a single array with careful ordering.
Code Template
// Longest common subsequence
function longestCommonSubsequence(text1, text2) {
const m = text1.length, n = text2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Unique paths in grid
function uniquePaths(m, n) {
const dp = Array.from({ length: m }, () => new Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
// Edit distance (Levenshtein)
function minDistance(word1, word2) {
const m = word1.length, n = word2.length;
const dp = Array.from({ length: m + 1 }, (_, i) =>
new Array(n + 1).fill(0).map((_, j) => (i === 0 ? j : j === 0 ? i : 0))
);
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}