Grid DP: Paths, Obstacles, Collect-Maximum
What This Concept Is
A right/down grid has an acyclic dependency order: row+column increases on every move. The state can be a cell if all relevant history is summarized by that position. Obstacles and cell rewards change values and transitions; keys, fuel, direction-dependent penalties or multiple agents may require more state.
Path counting sums disjoint predecessor classes. Maximum-reward paths maximize over reachable predecessors and then add the current cell reward. Empty grids, blocked endpoints, negative rewards and movement rules belong in the contract.
Why It Matters Here
This exposes the distinction between a valid value zero and an unreachable state. It also connects the previous graph module to DP: a rectangular drawing does not make a graph acyclic. Four-direction moves can create cycles, requiring a different state or algorithm.
Concrete Examples
Counting. For a 3-by-3 grid with only the center blocked, start (0,0),
end (2,2), count table rows are [1,1,1], [1,0,1], [1,1,2].
The answer 2 counts one route across the top/right boundary and one along
the left/bottom boundary. A blocked start must be set to 0, overriding the
usual single empty-prefix path. A 1-by-1 unblocked grid has exactly one path.
With no obstacles and positive dimensions R,C, the answer is
choose(R+C-2,R-1): choose which moves are downward. This provides an independent
check, but ceases to describe arbitrary obstacle layouts.
Negative rewards. For [[-5,-2],[-3,-4]], counting both endpoint rewards,
the best total is -11 via right then down. Initializing missing predecessors
to zero would allow a path to start in the middle. Use an unreachable marker,
and initialize only the actual start to its reward. A blocked destination returns
unreachable, not an invented reward-zero path.
Extra state. Suppose entering a cell can consume the only obstacle-removal
token. Two paths reaching the same cell can have different remaining budgets.
State (row,column,token_used) preserves that information. The number of
states and candidate moves grows with the token budget dimension.
Common Confusion / Misconceptions
Allowing left/up as well introduces cycles. For unweighted shortest paths,
BFS handles those moves; for weighted paths, choose an algorithm under its
weight assumptions. Counting unrestricted walks can be infinite. Counting
simple paths requires remembering visited vertices or another structural argument.
Replacing min by max on a cyclic recurrence is not a complete solution.
How To Use It
Specify dimensions, moves, start/end, obstacles and reward accounting. Derive the predecessor set and a rank proving acyclicity. For counts use zero for impossible states; for max reward use an explicit unreachable marker. Keep parents if a path is required. Row compression costs O(C) values, but counts may have many bits and path recovery requires additional information.
Check Yourself
Why is an empty path at an unblocked 1-by-1 grid counted once? Which initialization fails on all-negative rewards? Does drawing a graph as a grid imply DAG structure?
Mini Drill or Application
Block both (0,1) and (1,0) in a 2-by-2 grid. Report count and max reward
for any rewards. Feedback: count 0, reward unreachable. Now unblock (1,0)
and trace the unique down/right path, including both endpoint rewards.
Read This Only If Stuck
Competitive Programming: grid-path exercises under dynamic programming. Locate by topic in the edition available locally; apply this page's boundary and movement contract explicitly.