Grid DP solves dynamic programming problems where states are cells in a grid.
It is useful because the state and transitions are easy to visualize.
Core Idea
Each cell stores an answer for reaching, counting, or optimizing up to that position. The transition usually depends on nearby cells, such as the cell above, below, left, or right.
The allowed movement directions determine the valid dependencies.
Grid DP works cleanly when movement directions create an acyclic computation order. For example, if movement is only right and down, each cell depends only on cells above or to the left.
Function Contract
min_path_sum(grid) expects a non-empty rectangular grid of numbers.
It returns the minimum cost to move from the top-left cell to the bottom-right cell when movement is only down or right. Empty grids and jagged rows are outside this example’s input contract.
Python Example
def min_path_sum(grid):
rows = len(grid)
cols = len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue
best = float("inf")
if r > 0:
best = min(best, dp[r - 1][c])
if c > 0:
best = min(best, dp[r][c - 1])
dp[r][c] = best + grid[r][c]
return dp[-1][-1]The example assumes movement only down or right.
State and Transition
For the example:
dp[r][c] = minimum cost to reach cell (r, c)The last move into (r, c) must come from above or from the left, so:
dp[r][c] = grid[r][c] + min(dp[r - 1][c], dp[r][c - 1])Boundary cells have only one possible predecessor.
Complexity
For a grid with rows * cols cells, the example fills each cell once and does constant work per cell. The time complexity is O(rows * cols), and the DP table also uses O(rows * cols) space.
Some grid DP solutions can compress memory to one row when each cell only depends on the previous row and current row.
Obstacles
If some cells are blocked, the transition must skip them:
if blocked[r][c]:
dp[r][c] = float("inf")The exact base case changes when the start or destination can be blocked.
Failure Example
A row-by-row grid DP is invalid when movement can go up, down, left, and right freely. A cell might then depend on a future cell that has not been computed yet.
In that situation, the problem is usually a graph traversal or shortest-path problem, not a simple acyclic grid DP.
Common Confusions
Grid DP needs an acyclic dependency order. If movement can go in all directions, a simple row-by-row DP may not be valid.
Obstacles and boundary cells should be handled explicitly because they often change the base cases.
If movement can revisit cells freely, the problem may be a graph shortest path problem rather than a simple DP table.
When To Use It
Use grid DP for path counting, minimum path cost, maximum collected value, and grid problems where movement direction creates a clear computation order.
Before using it, check the movement rules. The DP order must compute every dependency before it is used.
The Main Point
Grid DP works when movement rules create an acyclic dependency order. If movement can cycle freely, the problem may be graph shortest path instead.