Lesson 29.2 · DP on Grids
Saving Memory: One Row Is Enough
When a cell needs only the row above and the cell to its left, a single 1D array updated left to right holds both.
8 min
Think of it like this
Writing on a single line of a whiteboard: before you overwrite a number, it still shows the value from the line above; the number you just wrote to its left is the current line's.
1.dp[c] before and after
Use dp[c] for the current row. At the moment you update dp[c], it still holds the value from the previous row ("above"), and dp[c − 1] already holds the current row's left neighbour. So dp[c] = dp[c] + dp[c − 1] (counting) or dp[c] = grid[r][c] + min(dp[c], dp[c − 1]) (cost).
Memory drops from O(m × n) to O(n). You lose the ability to reconstruct the path, so keep the full table when the path itself is needed.
Remember
- dp[c] = above, dp[c − 1] = left.
- O(n) memory.
- Full table if you need the path back.
Common mistakes
- Iterating right to left (then dp[c − 1] is still from the previous row).