Reuse instead of store
Many DP tables keep far more rows than the recurrence actually reads. If computing a row needs only the previous row, or the previous two, you can keep just those and overwrite them as you advance. This is the rolling array technique.
Two common forms
- Two rows. Keep a previous and a current row, swap them after each step. This suits grid problems where each cell reads only the row above.
- One row in place. When a cell reads its own row and the previous row, a single array can work if you choose the scan direction carefully, as in the one row knapsack.
The trick is to make sure that any old value you still need has not yet been overwritten when you read it. Scan direction is what protects those values.
Key idea
Rolling arrays cut DP memory by keeping only the recent rows the recurrence reads and overwriting the rest, with scan direction chosen so values are read before they are replaced.