LESSON 29 · PATTERN GUIDE

Grid DP

Compute paths or costs in a grid by combining answers from neighboring cells.

FIRST, LEARN THE PATTERNDefine dp[row][col] for reaching or ending at a cell. Obstacles and boundaries determine which predecessor states contribute.

The task asks for paths, minimum cost, or largest structure in a matrix with local moves.

How to approach it

Choose a traversal order so predecessor cells are already solved; initialize the start cell and handle blocked cells explicitly.

Watch out for

The allowed movement directions determine whether simple row-by-row DP works. Some grid tasks require extra dimensions or different algorithms.

A CLOSER EXPLANATION

A grid DP state summarizes the routes or cost to reach one cell. If moves only come from above or left, row-major traversal ensures both predecessor answers are already known. Obstacles contribute no routes, while weighted cells add their cost during transitions.

NOW YOU TRY

Practice question

How many paths move only right or down from the top-left to the bottom-right of a 3×3 empty grid?

EXAMPLEgrid = 3 rows × 3 columnsGive your answer before revealing the explanation.

Show a hint

Each cell's path count is the sum from the cell above and the cell to the left.

Show an answer

6 paths.

CONNECT IT TO REAL LIFE

Grid DP at work

A warehouse robot starts at the top-left of a 3-by-3 aisle grid and may only move right or down. How many routes reach the bottom-right if no aisle is blocked?

Show one possible approach

6 routes. Every route contains two right moves and two down moves, so there are 6 distinct orderings of those moves.

Practice next

Use these problem IDs to find additional practice for this pattern:

626364221931120