Grid & Path DP · bigonotes

Grid DP answers questions about paths: how many there are, which is cheapest, or how likely you are to stay on the board. The state is your position, plus a move counter when the problem gives you a budget of steps. The same idea works on any small graph, such as the knight moves on a phone keypad.

The idea#

When moves only go one way (right/down, or one row down), every path into a cell comes from a few fixed neighbors. So the answer for a cell combines the answers for those neighbors:

Count paths: paths(r, c) = paths(r-1, c) + paths(r, c-1).
Cheapest path: cost(r, c) = grid[r][c] + min(cost(r-1, c), cost(r, c-1)).

This works because one-way moves never return to a cell, so the neighbors' answers are final before you need them.

That argument breaks when moves can go in any direction (a knight, or up/down/left/right), because positions alone can repeat. So add moves left to the state. Each call uses one move, so (r, c, moves) never cycles.

How to spot it#

Look for these signals in the question.

"Top-left to bottom-right", "only move right or down", "falling path".
"Exactly k moves", "at most maxMove moves", "probability it stays on the board".
A small fixed graph (keypad, chessboard) with "how many sequences of length n".

Template#

Here is the one-way shape. Off-grid cells are a base case that returns a neutral value, so they can never win.

best(r, c):
    if (r, c) is off the grid or blocked:
        return the neutral value      # inf for min, 0 for counts
    if (r, c) is the end cell:
        return its own value
    combine best(neighbor) for each allowed next cell
    add the value of (r, c) if the question has cell costs
    return that
memoize best on (r, c)
answer: best(start), or the best over every allowed start

The grid has $m \times n$ states and a few moves each, so the cost is $O(mn)$ .

With a move budget#

For the any-direction case from the idea above, moves joins the state. Check the off-grid case first, then the budget.

paths(r, c, moves):
    if (r, c) is off the grid:
        return the off-grid value     # 1 if leaving counts, else 0
    if moves == 0:
        return the on-grid value
    total = 0
    for each move (dr, dc):
        total = (total + paths(r + dr, c + dc, moves - 1)) % MOD
    return total

Pitfalls#

These mistakes cause the most wrong answers.

Applying the modulus only at the end. It works in Python only because integers don't overflow. Apply it at every step.
Checking moves == 0 before the off-grid check. A move that leaves the grid on the last step is then lost.
Using too few neighbors. Check which earlier cells can limit or feed the current one.
Moves in four directions with no budget. This works only when a rule (such as "strictly increasing") makes the graph acyclic.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Unique Paths

Count paths: paths(r, c) = paths(r-1, c) + paths(r, c-1). The first row and first column each have one path.

Hint: Unique Paths II

Same recurrence as Unique Paths. An obstacle cell has 0 paths.

Hint: Minimum Path Sum

Add the cell's cost to min(up, left). Off-grid neighbors return inf so they are never chosen.

Hint: Minimum Falling Path Sum

Start anywhere in the top row and move to one of the three cells below. Stepping off the side returns inf. The last row returns its own value. The answer is the min over every start column.

Hint: Maximal Square

Store the side of the largest all-1 square that ends at each cell. On a '1', it is min(left, up, diagonal) + 1, because the smallest neighbor limits the square. It needs all three neighbors, not two.

Hint: Knight Probability in Chessboard

Each of the 8 knight moves happens with probability 1/8, so prob(r, c, k) = sum(prob(next, k - 1) / 8). Off the board is 0. Still on the board with no moves left is 1. It is the counting recurrence with a weight on each move.

Hint: Out of Boundary Paths

The state is (r, c, moves). Off the grid returns 1: one escaping path. Inside with no moves left returns 0. Check off-grid before moves == 0, because leaving on the very last move still counts.

Hint: Knight Dialer

Write the keypad as an adjacency map (0 → [4, 6], 1 → [6, 8], ..., 5 → []). Then dial(node, n) = sum(dial(nb, n - 1) for nb in adj[node]) with dial(node, 0) = 1. Sum over the 10 start digits and apply the modulus at every addition.

Hint: Longest Increasing Path in a Matrix

Moves go in four directions with no budget. The "strictly increasing" rule means you never return to a cell, so the graph is acyclic. Use DFS with memo over that DAG; see Topological Sort.

Hint: Pascal's Triangle

Each row starts and ends with 1, and every inner cell is the sum of the two cells above it. Build row by row from the previous one.

Key takeaways#

One-way moves: the cell's answer combines a few fixed neighbors.
Any-direction moves: add moves left to the state so it can't cycle.
Off-grid is a base case: inf for min, 0 or 1 for counts depending on the question.
Probability DP is counting DP with a weight per move.
Apply the modulus inside the recurrence.

Core idea#

Grid DP counts paths, finds the cheapest one, or finds the chance of staying on the board. The state is your position, plus moves left when the problem gives a step budget.

Key points#

One-way moves (right/down, one row down): a cell combines a few fixed neighbors.
Count: paths(r, c) = paths(r-1, c) + paths(r, c-1).
Cheapest: cost(r, c) = grid[r][c] + min(cost(r-1, c), cost(r, c-1)).
Any-direction moves: add moves left to the state. Each call uses one move, so (r, c, moves) never cycles.
Off-grid is a base case: inf for min, 0 or 1 for counts.
The same idea works on a small graph, such as knight moves on a keypad.
Spot it: "only move right or down", "exactly k moves", "probability it stays on the board".

Variations#

Problem	State and recurrence
Unique Paths II	Obstacle cell has 0 paths
Maximal Square	`min(left, up, diagonal) + 1` on a `'1'`
Knight Probability	`sum(prob(next, k - 1) / 8)`; on board at 0 moves is 1
Out of Boundary Paths	Off grid is 1; inside with 0 moves is 0
Knight Dialer	`dial(node, n) = sum(dial(nb, n - 1))` over an adjacency map

Template#

best(r, c):
    if (r, c) is off the grid or blocked:
        return the neutral value      # inf for min, 0 for counts
    if (r, c) is the end cell: return its own value
    combine best(neighbor) for each allowed next cell
    add the value of (r, c) if cells have costs
memoize best on (r, c)
with a move budget: state is (r, c, moves); check off-grid first

Pitfalls#

Applying the modulus only at the end. Apply it at every step.
Checking moves == 0 before the off-grid check. Leaving on the last move still counts.
Maximal Square needs all three neighbors, not two.
Longest Increasing Path in a Matrix has four directions and no budget. It works only because "strictly increasing" makes the graph acyclic.

Say it in an interview#

"Moves go one way, so each cell depends only on its neighbors above and to the left."
"Moves go in any direction, so moves left is in the state and nothing cycles."