2-D Dynamic Programming

What it is

Some problems need two independent parameters to describe a subproblem — e.g. comparing two strings (dp[i][j] = answer using the first i characters of string A and first j of string B), or a grid (dp[row][col]). The DP table becomes 2-D instead of 1-D, but the same memoization/tabulation choice applies.

Common shapes

• Grid traversal — dp[row][col] built from dp[row-1][col] and dp[row][col-1] (paths from the top or left).
• Two-string comparison — longest common subsequence, edit distance: dp[i][j] relates to dp[i-1][j], dp[i][j-1], and dp[i-1][j-1].
• Knapsack — dp[item][capacity], deciding to include or exclude each item under a weight limit.

Space optimization

Since row i of the table often only depends on row i−1, the 2-D table can frequently be compressed to two 1-D rows (or even one, updated in place) — turning O(n·m) space into O(m).

Why 1-D DP comes first

The reasoning — find the recurrence, decide memoization vs. tabulation — is identical; 2-D DP is that same skill applied to a table indexed by two variables instead of one.