2D Dynamic Programming
Grid paths, longest common subsequence, and the knapsack - building a table where each cell depends on earlier ones.
On this page
When a problem's state needs two indices - a position in each of two strings, a cell in a grid, an item plus a remaining capacity - you get 2D dynamic programming. The idea is identical to 1D: define what each table cell means and how it depends on earlier cells. There are just two axes now, and the table is filled so every dependency is ready.
Grid paths: the gentlest 2D DP
"How many paths from the top-left to the bottom-right of a grid, moving only right or down?" The state is the cell; a cell is reachable from the cell above or the cell to its left, so its count is their sum:
// number of unique paths in an m x n grid — O(m*n)
int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1; // only one way down the first column
for (int j = 0; j < n; j++) dp[0][j] = 1; // only one way across the first row
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // from above + from the left
return dp[m-1][n-1];
}dp[i][j] = paths to reach cell (i, j); the transition sums the two cells you could have come from. The
base cases are the first row and column (only one path along an edge).
Two sequences: longest common subsequence
When the two indices are positions in two strings, you get the classic LCS - the longest
subsequence common to both. dp[i][j] is the LCS length of the first i chars of one string and first
j of the other:
// longest common subsequence length — O(m*n)
int lcs(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1]; // dp[0][*] and dp[*][0] = 0 (empty prefix)
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a.charAt(i-1) == b.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + 1; // chars match → extend
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // skip one char, take the best
return dp[m][n];
}The transition captures the choice: if the current characters match, extend the diagonal subproblem by one; otherwise, drop a character from one string or the other and take the better. This same match-or-skip shape underlies edit distance, longest common substring, and sequence-alignment problems.
The 0/1 knapsack
The knapsack packs items (each with a weight and value) into a capacity to maximize value. Its state is
two axes of a different kind: item index and remaining capacity - dp[i][w] = best value using the
first i items within capacity w, choosing for each item to take it or leave it. It's the template for
"pick a subset subject to a budget" problems.
Filling order and space reduction
Fill a 2D DP table so every cell's dependencies are already computed - usually row by row, left to right, since cells depend on those above and to the left. Many 2D DPs only ever look at the previous row, so you can reduce O(m*n) space to O(n) by keeping just one or two rows - a common follow-up optimization interviewers ask for.
A 2D DP table is a spreadsheet where each cell's formula references the cells directly above and to its left. You can't compute a cell until those it depends on are filled, so you work top-to-bottom, left-to-right, and by the time you reach any cell its inputs are ready. The first row and column are the 'given' base values you type in by hand; every other cell is a small formula combining its neighbors; and the bottom-right cell holds the final answer once the sheet is complete.
Given a grid of non-negative numbers, find the minimum sum along a path from top-left to bottom-right, moving only right or down. Define dp[i][j], the transition, and the base cases.
In the longest-common-subsequence DP, what does the transition do when the two current characters differ?
Key takeaways
- 2D DP uses a two-index state - positions in two strings, a grid cell, or item-plus-capacity - filled so every dependency is ready.
- Grid paths: dp[i][j] = dp[i-1][j] + dp[i][j-1] (sum of the two cells you could arrive from).
- Longest common subsequence: match → extend the diagonal (+1); differ → max of dropping a char from either string.
- 0/1 knapsack (item index x remaining capacity) is the template for 'pick a subset within a budget'.
- Fill row by row so dependencies are ready; many 2D DPs reduce to O(n) space by keeping only the previous row.