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.
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.
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.
Give them the value that can't affect the combine. Then the same line of code works on edges and next to rocks.
Set dp[0][0] directly. Don't hard-code the whole first row or column. That shortcut is where most rock bugs come from.
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.
| Problem | Combine | Rock |
|---|---|---|
| Count | + | 0 |
| Min cost | min | ∞ |
| Max coins | max | −∞ |
# 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