2D Grid Dynamic Programming deals with problems where decisions are made across a grid, moving from one cell to another while accumulating results. Each cell represents a state, and its value depends on previously computed neighboring cells, typically from the top, left, or other allowed directions.

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.

The reason this works is that movement constraints create a natural dependency structure. If you can only move right or down, then 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. But when the problem asks you to optimize something across all paths in a grid, DP is likely the right tool.

Here are the 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, think 2D grid DP immediately.

Every 2D grid DP problem follows the same blueprint. Once you internalize it, the pattern becomes second nature.

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, then you can only arrive at (i,j) from (i-1,j) (above) or (i,j-1) (left). The transition becomes:

The movement constraints directly determine the transition. If you could also move diagonally, you would add dp[i-1][j-1] to the mix.

3. Handle Base Cases

The first row and first column are special because cells there can only be reached from one 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. This is what makes the approach work. The filling order respects the dependency structure.

The base cases (first row and first column, shown in orange) are filled first. Interior cells (teal) are computed using already-filled neighbors. The answer sits at the bottom-right corner (green).

5. Space Optimization

Since each row only depends on the current row and the row above, you do not need the entire m x n table. You can use a single 1D array of size n and update it row by row. When processing row i, the array already holds values from row i-1. As you sweep left to right, dp[j-1] gives the left neighbor (already updated for row i), and dp[j] gives the top neighbor (still holding the value from row i-1). This reduces space from O(m * n) to O(n).

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.

Building the Intuition

Why does DP work here? 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.

And why not greedy? Imagine 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. We need to consider the full picture, which is exactly what DP does by building solutions bottom-up.

Step-by-Step Trace

Let us walk through a concrete example:

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) -> (1,0) -> (1,1) -> (1,2) -> (2,2) with costs 1 + 1 + 5 + 1 + 1 ... wait, that is 9, not 7. Let us trace more carefully. The path (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) gives 1 + 3 + 1 + 1 + 1 = 7. That is the optimal one.

Implementation

Complexity Analysis

Since each row only needs the previous row, we can compress the 2D table into a 1D array. Here is how it works in Java:

The key insight is that 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 is exactly what we need for the min(top, left) transition.