Throwing away the rows you no longer need

The stairs table holds n numbers. Look at what the loop actually reads:

ways[i] = ways[i - 1] + ways[i - 2]

Only the previous two. Everything before them is dead weight.

a, b = 1, 1
for i from 2 to n:
    a, b = b, a + b
return b

O(n) memory becomes O(1), two variables.

The general move

If a state depends only on the last k rows, keep k rows rather than all of them. For a grid where each cell needs the one above and the one to the left, you keep one row and update it in place, which takes memory from O(rows x cols) to O(cols).

That is often the difference between fitting in memory and not. A 10000 by 10000 table of 8-byte numbers is 800 MB; one row is 80 KB.

The cost, and it is a real one

Rolled tables are harder to debug, and they destroy the information needed to reconstruct the answer. Keeping the whole table lets you walk back through it and recover which choices produced the result. With two variables, the number survives and the path does not.

So:

• Need only the value, and memory is tight? Roll it.
• Need the actual subsequence, the actual items, the actual path? Keep the table.

There is a middle option worth knowing for an interview: compute the value with a rolled table, and if the path is needed, recompute it with the full table only once you know the answer is worth having.