This chapter focuses on identifying grid-based patterns, defining DP states, and building transitions based on valid moves.

2D grid DP is dynamic programming applied to a matrix, where the value at each cell depends on its neighbors. Typically, you define a state dp[i][j] that represents the answer to some question for the subproblem ending at row i, column j. You then fill the table by combining answers from adjacent cells.

Movement constraints create a natural dependency structure. If you can only move right or down, the answer at any cell depends only on the cell above it and the cell to its left. Those cells, in turn, depend on their own neighbors. This chain of dependencies is what makes DP applicable.

Each arrow shows a dependency. Cell (1,1) depends on (0,1) and (1,0). Cell (2,2) depends on (1,2) and (2,1). The starting cell (0,0) has no dependencies, it is the base case. The destination (2,2) is the final answer.

Not every grid problem needs DP. BFS and DFS handle reachability and connected components. When the problem asks you to optimize something across all paths in a grid, DP usually applies.

Signals to watch for:

If the problem asks "how many ways" or "what is the minimum/maximum cost" to traverse a grid with restricted movement, 2D grid DP is the likely approach.

Every 2D grid DP problem follows the same blueprint.

1. Define the State

Decide what dp[i][j] means. This is the most important step. For Minimum Path Sum, dp[i][j] is the minimum cost to reach cell (i,j) from (0,0). For Unique Paths, dp[i][j] is the number of distinct paths to cell (i,j).

2. Write the Transition

Figure out which cells contribute to dp[i][j]. If movement is restricted to right and down, you can only arrive at (i,j) from (i-1,j) (above) or (i,j-1) (left). The transition becomes:

Movement constraints determine the transition. If diagonal moves were allowed, the recurrence would also include dp[i-1][j-1].

3. Handle Base Cases

The first row and first column are special because cells there can only be reached from one direction. dp[0][0] is usually grid[0][0] itself, and the rest of the first row and column accumulate from a single direction.

4. Fill the Table

Process cells row by row, left to right. By the time you compute dp[i][j], both dp[i-1][j] and dp[i][j-1] are already computed. The filling order respects the dependency structure.

5. Space Optimization

Since each row only depends on the row above, space can be reduced from O(m * n) to O(n). See the Space-Optimized Version below for the implementation.

Problem Statement

Given an m x n grid filled with non-negative numbers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of all numbers along the path. You can only move right or down at each step.

Why DP Works

Consider any cell (i,j) that is not on the first row or first column. There are exactly two ways to arrive at it: from the cell above (i-1,j) or from the cell to the left (i,j-1). The minimum cost to reach (i,j) must come through whichever of those two neighbors has the lower cost. That is the optimal substructure.

Why not greedy? Consider a grid where the cell to the right is cheap but leads into an expensive column, while the cell below is slightly more expensive but leads to a very cheap row. A greedy algorithm that always picks the cheaper immediate neighbor would miss the globally optimal path. DP avoids this by building solutions bottom-up over the full table.

Step-by-Step Trace

Consider this grid:

Initialize dp[0][0]:

dp[0][0] = grid[0][0] = 1

Fill the first row (can only come from the left):

Fill the first column (can only come from above):

Fill the interior cells:

Final dp table:

The answer is dp[2][2] = 7. The optimal path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) with cell costs 1 + 3 + 1 + 1 + 1 = 7.

Implementation: Top-Down (Memoized Recursion)

The recursive formulation follows directly from the recurrence: at cell (i, j), the cost is grid[i][j] plus the minimum of the costs to reach (i-1, j) or (i, j-1). The memo caches each cell once.

Implementation: Bottom-Up (Tabulation)

The iterative version fills the table in the same order as the trace: first row, first column, then interior cells row by row.

Complexity Analysis

Since each row only needs the previous row, the 2D table can be compressed into a 1D array. The Java version:

When processing dp[j] for row i, the array is in a mixed state. dp[j] itself still holds the value from row i-1 (the top neighbor), while dp[j-1] has already been updated to row i (the left neighbor). This matches the min(top, left) transition.

Minimum Path Sum used the obvious state: dp[i][j] = the answer at cell (i, j). The recurrence followed directly because every path to (i, j) extends a path to (i-1, j) or (i, j-1).

Maximal Square teaches a less obvious state-design move that comes up repeatedly in grid DP: when the answer is the size of the largest shape, the natural state is "size of the largest shape ending at this cell."

Problem Statement

Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

Why The Obvious State Fails

A first instinct is dp[i][j] = "area of the largest square in the sub-grid [0..i][0..j]." This is monotone in (i, j), so the recurrence would be dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1], (square ending at (i,j)?)).

The trouble is the last term: computing "square ending at (i, j)" requires scanning upward and leftward from (i, j) to find the largest all-ones square with (i, j) as the bottom-right corner. The scan is O(min(i, j)) per cell, giving O(m n min(m, n)) overall.

The fix is to change what dp[i][j] means.

The State-Design Move

Let dp[i][j] = the side length of the largest all-ones square that has (i, j) as its bottom-right corner. This is a different question from "the answer at cell (i, j)." It is a strictly local property of (i, j) and its three neighbors above, to the left, and to the upper-left.

If grid[i][j] == 0, then no square ends at (i, j), so dp[i][j] = 0.

If grid[i][j] == 1, then (i, j) is the bottom-right corner of some all-ones square (at least 1x1). Extending it to size s requires the three squares of size s - 1 ending at (i-1, j), (i, j-1), and (i-1, j-1) to all be at least s - 1. The largest valid s is:

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

The min is the bottleneck: the square ending at (i, j) cannot be larger than the smallest of the three squares ending at its three neighbors. The +1 extends each of those squares down-and-right by one to include (i, j).

The final answer is the maximum value in the entire dp table, squared (to convert from side length to area).

Why The Three Neighbors

Consider dp[i-1][j-1] = 3, dp[i-1][j] = 4, and dp[i][j-1] = 4. The three regions look like:

An all-ones 4x4 square anchored at (i, j) requires every cell in (i-3..i, j-3..j) to be 1. The 3x3 anchored at (i-1, j-1) only guarantees (i-3..i-1, j-3..j-1). The cells (i-3..i-1, j) and (i, j-3..j-1) are covered by the other two squares, but the upper-left 3x3 region is the limiting factor.

So the largest guaranteed square is bounded by min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

Walkthrough

Consider this grid:

Fill the dp table from top-left to bottom-right. Base cases are the top row and left column, where dp[i][j] = grid[i][j] since no square larger than 1x1 can end there.

Working through the interesting cells:

The maximum value in dp is 2, so the largest square has side 2 and area 4.

Implementation: Top-Down (Memoized Recursion)

The recursive form computes the side length of the largest all-ones square ending at (i, j) by asking the same of its three neighbors. The answer is the maximum over all cells, tracked as a global during the recursion.

Implementation: Bottom-Up (Tabulation)

The iterative version fills the dp table left-to-right, top-to-bottom, tracking the best side length seen so far.

The General Lesson

When the answer asks for the "largest shape" or "longest sequence" of a particular kind, the natural state is often "the size of the shape ending at this cell," not "the answer over the sub-grid." The ending-at framing turns the recurrence into a strictly local check on a small set of neighbors, which is what makes the O(m * n) bound achievable. The same idea appears in:

If a grid DP looks expensive because each cell needs to look back across a large region, try redefining the state to "shape ending at this cell." When the shape's geometry is constrained enough (squares, increasing sequences), the recurrence usually collapses to a function of a few neighbors.

Space Optimization

Maximal Square also admits the same 1D space optimization as Minimum Path Sum. The recurrence reads dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. After updating dp[j], we have lost dp[i-1][j-1] for the next column. The fix is to save it in a temporary variable before the update:

The diagonal neighbor is the only thing that pushes the 1D compression beyond what Minimum Path Sum needs. This is the most common 1D-compression pitfall in grid DP: any recurrence that reads dp[i-1][j-1] requires a separate diagonal cache.