Grid Path DP Trainer

Every cell asks one question: how did I get here? Only from above or from the left. You fill the table, and the code shows which line you just ran.

The recipe you can reuse for every grid DP

1. Name the cell

dp[i][j] = the answer if the grid ended at (i, j): ways to reach it, cheapest cost to reach it, most coins on arrival.

2. Look up and left

Moves are right or down, so you can only arrive from (i−1, j) or (i, j−1). Combine those two: add, min, or max.

3. Rocks and off-grid get the identity

Give them the value that can't affect the combine. Then the same line of code works on edges and next to rocks.

4. Seed only the start

Set dp[0][0] directly. Don't hard-code the whole first row or column. That shortcut is where most rock bugs come from.

5. Fill in dependency order

Any order works as long as top and left are done before the cell. Row by row is the usual choice. That's also why a single row is enough memory.

Identity per problem
ProblemCombineRock
Count+0
Min costmin∞
Max coinsmax−∞
# The bug: pre-filling edges ignores rocks
for j in range(n): dp[0][j] = 1
for i in range(m): dp[i][0] = 1
# a rock at (0,2) still leaves dp[0][3] = 1. Wrong.
# The fix: one loop for every cell
top  = dp[i-1][j] if i > 0 else 0   # identity
left = dp[i][j-1] if j > 0 else 0
dp[i][j] = 0 if rock else top + left