Lesson

2D Dynamic Programming

The intuition: when one index isn't enough

In one-dimensional DP, the state was described by one number: "the best answer for the first i elements." Some problems need more than one number, because the answer depends on two quantities at once:

A grid. To describe where you're standing, you need a row i and a column j.
Two strings. You need to know how many characters are taken from the first string (i) and how many from the second (j).

Imagine filling in a spreadsheet. The formula in each cell refers only to its neighbors above, to the left, or diagonally. If you drag it across the whole sheet in the right order, the answer ends up in the bottom-right corner. That's exactly how 2D DP works.

A sign of 2D DP: if you find yourself saying "the answer for the first i characters of one string and the first j characters of the other," or "the answer for cell (i, j)," the state is two-dimensional.

Example 1: paths in a grid

Let's take a problem of our own (it's not in this chapter's practice set). A robot stands in the top-left corner of an n × m grid. In one move it can go right, down, or diagonally down-right. How many ways can it reach the bottom-right corner?

State: dp[i][j] is the number of ways to reach cell (i, j).

Transition: you can enter cell (i, j) only from its three neighbors:

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

Base case: the first row can only be reached by moving right, so it's all 1s. The first column can only be reached by moving down, so it's all 1s too.

Here's the table for a 3 × 4 grid:

i \ j	0	1	2	3
0	1	1	1	1
1	1	3	5	7
2	1	5	13	25

Let's check one cell: dp[2][2] = 5 (above) + 5 (left) + 3 (diagonal) = 13. The answer sits in the bottom-right corner and equals 25.

We fill row i = 2 from left to right. When the pointer is at j = 3, all three neighbors it needs are already computed:

132

j ↓ 253

Row i=2: dp[2][3] = 7 (above) + 13 (left) + 5 (diagonal) = 25

Code template

def count_paths(n, m):
    # dp[i][j] is the number of ways to reach cell (i, j)
    dp = [[1] * m for _ in range(n)]  # first row and column = 1
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]
    return dp[n-1][m-1]

Example 2: a common subsequence of two strings

There are two "axes" here too, but they're no longer cell coordinates; they're prefix lengths. A subsequence is a set of characters from a string in their original order, but not necessarily adjacent. State: dp[i][j] is the length of the longest common subsequence of the first i characters of string a and the first j characters of string b.

The key trick: add a row and a column for the empty prefix. The table becomes (len(a)+1) × (len(b)+1), and the zeroth row and column are filled with zeros, because an empty string shares no characters with anything. That way the base case sets itself up, and you don't have to handle i = 0 or j = 0 separately.

The table for a = "abc" and b = "ac":

	a	c
""	0	0
a	1	1
b	1	1
c	1	2

The answer is 2: the common subsequence "ac". Each cell again looks at its neighbors above, to the left, and diagonally. If characters a[i-1] and b[j-1] match, that's your cue to use the diagonal. You'll derive the exact formula yourself in the practice problems; now you know where to look for it.

Fill order

This is the central question of 2D DP: by the time you compute a cell, everything it depends on must already be computed.

Cell depends on	Traversal order
above, left, diagonal ↖	rows top to bottom, left to right within each row
below, right, diagonal ↘	rows bottom to top, right to left within each row

If a cell depends only on the previous row and on its left neighbor in the current row, you don't need to keep the whole table. One or two rows are enough, and space drops from O(n·m) to O(m).

Complexity

Time: O(n · m). Each cell is computed once in O(1).
Space: O(n · m) for the full table, O(m) with the row optimization.

How it sounds in an interview

"The state is dp[i][j]: the answer for prefixes of length i and j. The transition takes values from above, the left, and the diagonal. The base case is the empty prefix, the zeroth row and column. I fill it row by row, left to right, and the answer is in dp[n][m]. Time is O(nm), and space can be compressed to a single row."

Say this before you start writing code. The interviewer will see right away that you understand the structure of the solution and aren't guessing at a formula.

Common mistakes

Index confusion. With a table of size n+1, the character for dp[i][j] is a[i-1], not a[i].
A forgotten base case. The zeroth row and column are filled incorrectly, and the error spreads across the whole table.
The wrong traversal order. A cell reads a neighbor that hasn't been computed yet.
Mixing up n and m. It's especially easy to do when creating the array: [n][m] versus [m][n].
Overflow. The number of paths grows very fast, so use long.
Compressing to one row without checking. The diagonal value dp[i-1][j-1] gets overwritten before you read it. Save it in a temporary variable.

Now you have a working recipe: two indices, a table, base cases along the edges, and the right traversal order.