Skip to main content

Grid DP: Paths, Obstacles, Collect-Maximum

What This Concept Is​

Grid DP is 2D tabulation over a rectangular grid, where $dp[i][j]$ depends on a small number of neighbors -- typically $dp[i-1][j]$ and $dp[i][j-1]$ for a "right-or-down" movement model. The canonical problems:

  • Count paths. Number of monotonic paths from $(0,0)$ to $(m-1, n-1)$ moving only right or down.

$$dp[i][j] = dp[i-1][j] + dp[i][j-1], \quad dp[0][0] = 1.$$

Closed-form: $\binom{m+n-2}{m-1}$, but the DP generalizes to obstacles and costs where the binomial does not.

  • Paths with obstacles. Same recurrence, but $dp[i][j] = 0$ at any blocked cell.

  • Collect maximum value. Each cell has a value $g[i][j]$. Maximize collected sum along a monotonic path.

$$dp[i][j] = g[i][j] + \max\big(dp[i-1][j],\ dp[i][j-1]\big),$$

with appropriate boundary handling.

  • Min-cost path. Same shape, with min instead of max.

Grid DP generalizes to 4-direction movement (then it becomes shortest path on a graph -- see the DP-on-DAGs concept) and to extra state dimensions: carrying items, limited fuel, two agents (cherry pickup), colored cells, health budget, and so on. Each extra state dimension multiplies the table size.

Grid DP is also the on-ramp for memoization vs tabulation: the natural row-major tabulation is so clean that students often skip memoization entirely. Tabulation naturally supports rolling-array reductions -- keep only the previous row for $O(n)$ space.

Why It Matters Here​

Grid DP is the cleanest visual of a tabulated recurrence. You can literally draw the table, point at $dp[i-1][j]$ and $dp[i][j-1]$, and watch the numbers grow. It is also the natural on-ramp to 2D DP before tackling sequence alignment, interval DP, and bitmask DP.

In interviews and real projects, grid DP shows up as pathfinding with constraints, simple dynamic-path planners, and image-processing dynamic-programming filters -- seam carving (Avidan & Shamir) is a famous example: remove low-energy vertical/horizontal seams from an image, each seam computed as a min-cost path through the grid.

Concrete Examples​

Example 1: Count paths in a $3 \times 3$ grid, no obstacles.

j=0j=1j=2
i=0111
i=1123
i=2136

Answer: $6$ paths from top-left to bottom-right. Verify: $\binom{4}{2} = 6$. ✓

Example 2: Collect-maximum with values

1 3 1
1 5 1
4 2 1

Fill $dp$:

 1  4  5
 2  9 10
 6 11 12

Maximum collectable = $12$, via path 1 -> 3 -> 5 -> 2 -> 1 (or 1 -> 1 -> 5 -> 2 -> 1, etc., all summing to $12$ in this mirror case -- the reconstruction chooses one).

Example 3: Paths with obstacles. Grid

0 0 0
0 1 0
0 0 0

(where 1 is blocked). Count paths:

012
0111
1101
2112

Answer: $2$.

Common Confusion / Misconceptions​

"Base cases are trivial." The first-row and first-column base cases are where most bugs live. For path count, $dp[0][j] = 1$ only if no obstacle blocks the way; otherwise the rest of row $0$ past the obstacle must be $0$. Forgetting this is a common cause of inflated answers.

"Counting and optimizing use the same recurrence." The recurrence shape is the same, but the operations are different. Counting uses $+$; optimizing uses max/min. Do not copy-paste across them without re-deriving. A particularly sneaky bug: copy a count recurrence into an optimize problem and forget to change the + to max, producing answers that are sums of path lengths rather than max-collect values.

"Multiple agents are just $k$ independent DPs." For $k$ agents walking the same grid with shared state ("cherry pickup"), the state must include all $k$ positions, because the reward depends on joint coverage. Two agents give state $(i_1, j_1, i_2, j_2)$; if both start at $(0,0)$ and move right/down at the same pace, $i_1 + j_1 = i_2 + j_2$ reduces to $(i_1, j_1, i_2)$, an $O(m^2 n)$ state.

"Diagonal moves don't change the DP." They do: with three incoming directions $(i-1, j), (i, j-1), (i-1, j-1)$, the recurrence still works but the path count doubles into Delannoy numbers; the optimizer uses a three-way max or min. Make sure your initialization handles the new diagonal base cases.

How To Use It​

  1. Declare grid cell states and their meanings (cell = position, or cell = position + carry?).
  2. Identify the small set of neighbors that $dp[i][j]$ reads.
  3. Write base cases along boundaries, with obstacle handling if applicable.
  4. Fill in the natural row-major order and read the final cell.
  5. Reconstruct if needed, by reversing the max/min argument at each step.
  6. Space-reduce to a single rolling row if you do not need reconstruction.
  7. If 4-direction movement or general weights appear, switch to Dijkstra / BFS -- you have left DP-on-DAGs territory.

Transfer / Where This Shows Up Later​

  • S3 Software Design. The "Strategy" + "Template Method" combo -- one fill_cell abstract method specialized per grid variant (count, max, min, obstacle) -- is a recurring pattern for grid DP families.
  • S5 Networking. Multi-path routing with per-hop cost on a grid topology (data-center fabrics) is solved with grid DP when the topology is monotonic and a superset of Dijkstra when not.
  • S6 Databases. Cost-based join enumeration over a join tree sometimes reduces to grid DP when joins commute only along monotonic orderings.
  • S7 Architecture. Capability matrices (roles × resources) optimized under policy constraints are grid DPs -- "what's the min-cost assignment that respects all rules?"
  • Phase 7 AI. Gridworld is the standard RL pedagogical environment precisely because its DP is transparent. Value iteration over a grid is the direct generalization of this concept with stochastic transitions.

Check Yourself​

  1. Why is "right-or-down" movement the canonical grid-DP shape?
  2. How does the recurrence change if diagonal moves are also allowed?
  3. If each cell may be visited at most $k$ times (unlikely in a monotonic walk but common in general graphs), does grid DP still apply?
  4. For count paths with obstacles, what is the base case for a blocked cell in row 0?
  5. Why does cherry pickup's state reduce from 4-dimensional $(i_1, j_1, i_2, j_2)$ to 3-dimensional $(i_1, j_1, i_2)$?
  6. When does grid DP break down and you must switch to Dijkstra or BFS?

Mini Drill or Application​

  1. Implement path count on an $m \times n$ grid; extend to allow obstacles marked 1 in a parallel array.
  2. Implement min-cost path with per-cell cost, where moves are right or down.
  3. Implement "cherry pickup" -- two agents walk from $(0,0)$ to $(m-1, n-1)$ (both right/down) and the combined path picks up each cherry at most once. Hint: state is $(i_1, j_1, i_2)$ because $i_1 + j_1 = i_2 + j_2$ at every step.
  4. Space-reduce each to a single rolling row and confirm answers match.
  5. Seam carving lite: given an $m \times n$ energy grid, find the minimum-energy vertical seam (one cell per row, adjacent cells at most one column apart).
  6. Dungeon-game min-HP: find minimum starting HP to reach $(m-1, n-1)$ where each cell adds or removes HP. Hint: fill the DP from bottom-right, not top-left.

Read This Only If Stuck​