One-dimensional DP tracks a single index along an array. But many problems live on a grid: a robot navigating cells, a path through a matrix, the cheapest route across a map. The state needs two indices - a row and a column - and the recurrence relates each cell to its neighbors. Welcome to 2D DP, where the table you fill is literally a 2D grid that mirrors the problem's geometry.

Grid path problems are the cleanest entry point. Imagine a robot at the top-left corner of an m x n grid that can only move down or right. How many distinct paths reach the bottom-right corner? You could try recursion: from (i, j), the robot reaches the goal in paths(i+1, j) + paths(i, j+1) ways. But that recursion explodes exponentially because the same subproblems get recomputed millions of times.

The Recurrence

Define dp[i][j] as the number of unique paths from (0, 0) to (i, j). The robot can only arrive at (i, j) from one of two cells: directly above (i-1, j) or directly to the left (i, j-1). So:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

The base cases are the top row and the left column. There is exactly one way to reach any cell in the top row - keep moving right. Same for the left column - keep moving down. So dp[0][j] = 1 for all j and dp[i][0] = 1 for all i.

Filling the Table

For a 3 by 3 grid:

1 1 1
1 ? ?
1 ? ?

Fill cell (1,1) first: dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2. Then (1,2) = dp[0][2] + dp[1][1] = 1 + 2 = 3. Then row 2 the same way:

1 1 1
1 2 3
1 3 6

The answer for a 3x3 grid is dp[2][2] = 6. Six unique paths from corner to corner.

See the grid fill cell by cell as each entry sums the paths from above and from the left:

Minimum Path Sum: A Variant

Same grid, but now each cell holds a cost and you want the minimum cost path from top-left to bottom-right. The recurrence changes from sum to min:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

The base cases are running sums of the top row and left column. Same table-filling order, same O(m * n) time. The 2D structure is identical - only the operator inside the recurrence changes.

Watch the minimum path sum table fill as each cell picks the cheaper neighbor:

Why This Works

The grid forces a topological order on subproblems: (i, j) depends only on cells with smaller i or smaller j. If you fill row by row, left to right, every dependency is already computed when you need it. This is the same principle as 1D DP - solve smaller subproblems first - but extended to two dimensions.

Each cell takes O(1) work because the recurrence reads exactly two neighbors. With m * n cells, the total time is O(m * n) and the table itself uses O(m * n) space.

Edit distance - also called Levenshtein distance - is the minimum number of single-character edits required to convert one string into another. The allowed edits are insert, delete, and replace. This is the algorithm behind spell checkers, DNA sequence alignment, fuzzy search, and the diff tool. It is the canonical 2D string DP and you will see it constantly in interviews.

The brute-force recursion tries every edit at every position and is exponential. The DP transforms it into O(m * n) by storing answers for every prefix pair.

Defining the State

Let dp[i][j] = minimum edits to convert word1[0:i] (the first i characters of word1) into word2[0:j] (the first j characters of word2). The final answer lives at dp[m][n] where m = len(word1) and n = len(word2).

Base Cases

To convert an empty string to a j-character string, you must insert j characters: dp[0][j] = j. To convert an i-character string to an empty string, you must delete i characters: dp[i][0] = i.

These base cases form the top row and left column of the table.

The Recurrence

Look at the last characters: word1[i-1] and word2[j-1].

Case 1: characters match. If word1[i-1] == word2[j-1], the last character costs nothing - it is already correct. The answer is whatever it took to align the prefixes:

dp[i][j] = dp[i-1][j-1]

Case 2: characters differ. You must perform exactly one edit, then solve a smaller subproblem. There are three choices:

• Replace word1[i-1] with word2[j-1], then align word1[0:i-1] with word2[0:j-1]. Cost: 1 + dp[i-1][j-1].
• Delete word1[i-1], then align word1[0:i-1] with word2[0:j]. Cost: 1 + dp[i-1][j].
• Insert word2[j-1] at the end of word1, then align word1[0:i] with word2[0:j-1]. Cost: 1 + dp[i][j-1].

Take the minimum:

dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

Worked Example

Convert "horse" to "ros". The table is 6x4 (lengths 5 and 3, plus the empty-string row/column):

1      ""  r  o  s
2  ""   0  1  2  3
3   h   1  1  2  3
4   o   2  2  1  2
5   r   3  2  2  2
6   s   4  3  3  2
7   e   5  4  4  3

The bottom-right cell is 3. Three edits convert "horse" to "ros": replace h with r, delete r, delete e.

Reading the Three Operations

The three predecessors of dp[i][j] correspond to the three edit operations. Memorize this mapping - it appears in every variant of the problem:

• dp[i-1][j-1] (diagonal) - replace (or match if characters are equal)
• dp[i-1][j] (above) - delete from word1
• dp[i][j-1] (left) - insert into word1

Once you internalize this geometry, edit distance variants (with different cost weights, restricted operations, etc.) become trivial - you just adjust which neighbors are eligible and what their costs are.

Step through the edit distance table as it computes the cost of transforming one string into another:

The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both strings in the same relative order, but not necessarily contiguously. For "abcde" and "ace", the LCS is "ace" of length 3. For "abc" and "def", there is no common character, so the LCS is the empty string of length 0.

LCS shows up in version control diff tools (computing the longest common run of unchanged lines), in bioinformatics (aligning DNA strands), and in text similarity scoring. Like edit distance, it is the second canonical 2D string DP - and the two problems share the same table geometry.

Defining the State

Let dp[i][j] = length of the LCS of text1[0:i] and text2[0:j]. The answer lives at dp[m][n].

Base Cases

Empty strings have no common subsequence: dp[0][j] = 0 for all j, and dp[i][0] = 0 for all i. The top row and left column are all zeros.

The Recurrence

Look at the last characters of the two prefixes.

Case 1: characters match. If text1[i-1] == text2[j-1], this character extends the LCS of the smaller prefixes by 1:

dp[i][j] = dp[i-1][j-1] + 1

Case 2: characters differ. You must drop one character from one of the strings and continue. Take the better of the two choices:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

dp[i-1][j] means "drop text1[i-1] and find LCS of the smaller text1 with full text2." dp[i][j-1] is the symmetric option. The max picks whichever drop leaves more LCS to discover.

Worked Example

For text1 = "abcde" and text2 = "ace":

1      ""  a  c  e
2  ""   0  0  0  0
3   a   0  1  1  1
4   b   0  1  1  1
5   c   0  1  2  2
6   d   0  1  2  2
7   e   0  1  2  3

The bottom-right cell is 3 - the length of "ace". Trace the diagonal jumps to see how a, then c, then e each extended the LCS.

See how matching characters trigger diagonal jumps while mismatches take the better of two neighbors:

Why max Instead of Sum

LCS is an optimization problem (find the longest), so the mismatch case takes max - pick the better branch. Unique paths is a counting problem, so the recurrence sums disjoint cases. Edit distance is also optimization (find the minimum), so it takes min. This sum/max/min distinction is the most important pattern in DP. Always identify which kind of problem you have before writing the recurrence.

Connection to Edit Distance

LCS and edit distance are tightly linked. If you allow only insertions and deletions (no replacements), the minimum edit distance equals m + n - 2 * LCS(word1, word2). The LCS is the part you keep; everything else is deleted from one string and inserted into the other. This duality gives you a sanity check: solve the same example with both algorithms and verify the relationship.

Edit distance and LCS are not isolated tricks. They are instances of a single pattern: two-string DP. Whenever a problem asks you to compare two strings or find some optimal alignment between them, your default move should be to define dp[i][j] over the two prefixes and look at the relationship between the last characters of each prefix.

The Template

Every two-string DP follows this skeleton:

The three pieces that change between problems:

1. Base cases - what does dp[i][0] and dp[0][j] mean for empty prefixes?
2. Match case - how does dp[i][j] build on dp[i-1][j-1] when characters agree?
3. Mismatch case - which combination of dp[i-1][j], dp[i][j-1], dp[i-1][j-1] does the recurrence use, and with what cost?

Comparing Edit Distance and LCS

Notice the symmetry. Both problems use the same (m+1) x (n+1) table, the same row-major fill order, and the same O(m * n) time. The only differences are which neighbors the recurrence reads and what arithmetic it applies. Once you see this pattern, you can solve nearly any string-comparison DP.

Other Two-String DP Problems

The same template solves many variants:

• Distinct subsequences - count how many ways text2 appears as a subsequence of text1. Match case adds dp[i-1][j-1] (use this match) plus dp[i-1][j] (skip this character of text1).
• Interleaving string - given s1, s2, s3, decide whether s3 is formed by interleaving s1 and s2. State: dp[i][j] is true if s1[0:i] and s2[0:j] interleave to form s3[0:i+j].
• Wildcard matching - match a string against a pattern containing ? and *. State: dp[i][j] is true if s[0:i] matches pattern[0:j].
• Regular expression matching - same template, with extra branches for * quantifiers.
• Shortest common supersequence - the shortest string that has both inputs as subsequences. Length equals m + n - LCS(s1, s2).

Each of these is just a different choice of base case, match case, and mismatch case. The skeleton is identical.

When to Reach for This Pattern

The trigger phrases in problem statements are:

• "minimum cost to transform one string to another"
• "longest common ___ of two strings"
• "number of ways to align two sequences"
• "is one string a subsequence/interleaving/match of another"

Whenever you see two strings and any kind of alignment or comparison question, default to defining dp[i][j] over the two prefixes and ask: "What is the relationship between the last characters?" The answer almost always yields the recurrence.

Every 2D DP recurrence we have seen reads only from the previous row and the current row. dp[i-1][j], dp[i-1][j-1], and dp[i][j-1] are all in row i-1 or in row i to the left of the current column. The rows above row i-1 are never touched again. This means storing the entire (m+1) x (n+1) table is wasteful - you can keep only the two rows you need.

For 1000-character strings, the full table is roughly 4 megabytes. Two rows is 8 kilobytes. That is a 500x reduction in memory with no change to the algorithm's correctness or asymptotic time complexity.

The Two-Row Approach

Maintain two arrays: prev (the previous row) and curr (the current row being filled). At the start of each new row, swap them and overwrite curr.

Notice the swap at the end of each row. After the swap, prev holds the row just completed and curr is ready to be overwritten for the next row. Memory usage is O(n) regardless of m.

The Single-Row Trick (Even Better)

For some recurrences you can collapse to a single row. The key insight: when filling curr[j], you need prev[j-1], prev[j], and curr[j-1]. If you process j left to right, curr[j-1] is already updated, but prev[j-1] is about to be overwritten by curr[j]. So you save prev[j-1] in a temporary variable before overwriting:

The single variable prev_diag plays the role of dp[i-1][j-1] from the previous row. This compresses the table to O(n) total space - half of what the two-row approach uses, and a 1000x improvement over the full table for length-1000 strings.

When You Cannot Optimize

Space optimization works for forward computation of the answer but breaks reconstruction. If the problem asks for the actual LCS string or the actual edit sequence (not just the length or count), you need the full table to traceback. Discarding old rows means the trace path is gone.

The rule of thumb:

• Need just the answer value - use space optimization, save memory.
• Need to reconstruct the solution - keep the full table.
• Memory-constrained - use Hirschberg's algorithm, which combines divide-and-conquer with O(n) space to get both the LCS string and the optimal space.

Choosing the Smaller Dimension

If m and n differ significantly, optimize against the smaller one. For example, comparing a 1,000,000-character document to a 100-character query, define your DP rows over the query (length 100) and iterate over the document. This gives O(100) memory instead of O(1,000,000). The recurrence and answer are the same - only the orientation flips.

Practice

Apply 2D DP to three classic problems. Start with unique paths (the cleanest grid DP), then edit distance (the canonical string DP), then LCS (the most reused two-string template).