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.
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.
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.
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.