2D DP

Two-dimensional DP uses a state that depends on two indices (or two dimensions), such as dp[i][j]. It appears when the subproblem is naturally defined over two independent variables: two positions in two sequences, row and column in a grid, or “item index” and “capacity” in a knapsack. This article explains when to use 2D DP, how to define state and transitions, and how to implement and optimize it.

When to Use 2D DP

Use 2D DP when:

Two sequences: The problem involves two arrays or strings (e.g. longest common subsequence, edit distance). One index per sequence.
Grid / matrix: The problem is on a 2D grid (e.g. number of paths, min path sum). Indices are row and column.
Two factors: The problem has two independent factors (e.g. “first i items” and “capacity w” in knapsack). One index per factor.

If one index is enough to express the subproblem (e.g. “answer for prefix [0..i]”), prefer 1D DP.

State Definition: What Does dp[i][j] Mean?

Define exactly what dp[i][j] represents. Common conventions:

Two sequences: dp[i][j] = answer for prefixes s[0..i) and t[0..j) (often length i and j). Sometimes “up to and including” i and j; be consistent.
Grid: dp[i][j] = answer for the subgrid from origin to cell (i, j) (e.g. number of paths to (i,j), or min cost to reach (i,j)).
Knapsack: dp[i][w] = best value using first i items and capacity w.

The recurrence must use only “smaller” states (e.g. smaller i/j, or smaller w), and the final answer should be a single cell or a simple aggregate.

Pattern 1: Two Sequences (Strings / Arrays)

Classic applications: Longest Common Subsequence (LCS), Edit Distance (Levenshtein). The state is “answer for first i chars of s and first j chars of t”.

Longest Common Subsequence (LCS)

Given two strings s and t, find the length of the longest subsequence that appears in both (order preserved; not necessarily contiguous).

State: dp[i][j] = length of LCS of s[0..i) and t[0..j).
Transition:
- If s[i-1] == t[j-1]: we can extend the LCS by one: dp[i][j] = 1 + dp[i-1][j-1].
- Else: we skip one character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Base: dp[i][0] = 0 for all i, and dp[0][j] = 0 for all j (empty string has LCS length 0).
Answer: dp[len(s)][len(t)].

Java
public int longestCommonSubsequence(String s, String t) {
    int n = s.length(), m = t.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

Iteration: row by row (or column by column). When computing dp[i][j], we need dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]; all are available if we iterate i from 1 to n and j from 1 to m.

Edit Distance (Levenshtein)

Minimum number of single-character edits (insert, delete, replace) to turn string s into string t.

State: dp[i][j] = minimum edits to change s[0..i) into t[0..j).
Transition:
- If s[i-1] == t[j-1]: no edit needed at this position: dp[i][j] = dp[i-1][j-1].
- Else we take the best of three options:
  - Replace s[i-1] with t[j-1]: cost 1 + dp[i-1][j-1].
  - Delete s[i-1]: cost 1 + dp[i-1][j].
  - Insert t[j-1]: cost 1 + dp[i][j-1].
- So dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Base: dp[i][0] = i (delete all of s[0..i)), dp[0][j] = j (insert all of t[0..j)).
Answer: dp[n][m].

Java
public int minDistance(String s, String t) {
    int n = s.length(), m = t.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    Math.min(dp[i - 1][j], dp[i][j - 1]),
                    dp[i - 1][j - 1]
                );
            }
        }
    }
    return dp[n][m];
}

Takeaway: For two sequences, indices usually represent lengths of prefixes; base cases are empty prefixes (row 0 and column 0).

Pattern 2: Grid / Matrix

Here the two dimensions are row and column. Common problems: number of paths, minimum/maximum path sum.

Unique Paths

From top-left (0,0) to bottom-right (m-1, n-1) on an m×n grid, only moving right or down. How many distinct paths?

State: dp[i][j] = number of ways to reach cell (i, j) from (0, 0).
Transition: We can arrive from above or from the left: dp[i][j] = dp[i-1][j] + dp[i][j-1].
Base: dp[0][0] = 1. For the first row and first column, only one way (all rights or all downs): dp[i][0] = 1, dp[0][j] = 1.
Answer: dp[m-1][n-1].

Java
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    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];
        }
    }
    return dp[m - 1][n - 1];
}

Minimum Path Sum

Same grid, but each cell has a cost. Find the path from top-left to bottom-right with minimum total cost (only right or down).

State: dp[i][j] = minimum sum of a path from (0,0) to (i,j).
Transition: We came from (i-1,j) or (i,j-1): dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
Base: dp[0][0] = grid[0][0]. First row: dp[0][j] = grid[0][j] + dp[0][j-1]. First column: dp[i][0] = grid[i][0] + dp[i-1][0].
Answer: dp[m-1][n-1].

Java
public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; i++) dp[i][0] = grid[i][0] + dp[i - 1][0];
    for (int j = 1; j < n; j++) dp[0][j] = grid[0][j] + dp[0][j - 1];
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

Takeaway: Grid DP usually fills row by row (and within row, column by column) so that dp[i-1][j] and dp[i][j-1] are ready.

Pattern 3: 0/1 Knapsack (Items × Capacity)

You have n items; item i has weight w[i] and value v[i]. Pack at most capacity W. Each item at most once. Maximize total value.

State: dp[i][w] = maximum value we can get using only the first i items and capacity w.
Transition:
- Skip item i-1: value = dp[i-1][w].
- Take item i-1 (only if w >= w[i-1]): value = v[i-1] + dp[i-1][w - w[i-1]].
- So dp[i][w] = max(dp[i-1][w], v[i-1] + dp[i-1][w - w[i-1]]) when w >= w[i-1], else dp[i][w] = dp[i-1][w].
Base: dp[0][w] = 0 for all w (no items ⇒ zero value).
Answer: dp[n][W].

Java
public int knapsack(int W, int[] weights, int[] values) {
    int n = weights.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weights[i - 1]) {
                dp[i][w] = Math.max(
                    dp[i][w],
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]
                );
            }
        }
    }
    return dp[n][W];
}

Iteration: for each i (items), iterate w from 0 to W. When computing dp[i][w], we only need row i-1; so we can optimize space to two rows or even one row (see below).

Base Cases and Iteration Order

Base cases in 2D DP are usually the first row and first column (e.g. empty string, empty set of items, or origin of the grid). Set them so the recurrence never reads invalid cells.
Iteration order: For two sequences and for knapsack, iterate i from 0 to n and j (or w) from 0 to m (or W). For grid, iterate row by row and column by column. Always ensure that when you compute dp[i][j], every cell it depends on has already been computed.

Space Optimization in 2D DP

Many 2D recurrences only use the previous row (and sometimes the current row up to the previous column). Then:

Two rows: Keep only dp[i-1] and dp[i] (e.g. prev[] and cur[]), and swap after each row. Space O(m) or O(n) instead of O(n×m).
One row (in-place): For knapsack, dp[i][w] only depends on dp[i-1][w] and dp[i-1][w - weight]. If we iterate w backward (from W down to 0), we can overwrite the same row and still read “previous” values. Space O(W).

Example: 0/1 Knapsack with one array:

Java
public int knapsackSpaceOptimized(int W, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    return dp[W];
}

Iterating w backward ensures that when we update dp[w], the value at dp[w - weights[i]] is still from the “previous” item round.

Summary Table: Classic 2D DP Problems

Problem	State	Transition idea	Order
LCS	LCS length of s[0..i), t[0..j)	match: 1+dp[i-1][j-1]; else max(omit s[i], omit t[j])	row by row
Edit Distance	min edits s[0..i)→t[0..j)	match: dp[i-1][j-1]; else 1+min(replace, delete, insert)	row by row
Unique Paths	ways to (i,j)	dp[i-1][j] + dp[i][j-1]	row by row
Min Path Sum	min sum to (i,j)	grid[i][j] + min(up, left)	row by row
0/1 Knapsack	best value with first i items, cap w	max(skip, take)	i 1..n, w 0..W

Practice Tips

Draw a small 2D table (e.g. 3×3) and fill base cases and a few cells by hand to validate the recurrence.
Use consistent indexing (0-based vs 1-based for lengths) and document it: e.g. “dp[i][j] uses lengths i and j”.
For two sequences, “empty prefix” (length 0) is usually the base row/column.
Consider space optimization only after the 2D version is correct; backward iteration for knapsack is a standard trick to remember.

Once you are comfortable with 2D state definition, transitions, and iteration order, you can tackle harder variants (e.g. multiple constraints, 3D DP) by adding more dimensions or more state.