One more kind of step

Suppose you can now climb 1, 2 or 3 stairs in one move. Does the whole approach change? Not at all. Ask about the last move again: you arrived from one, two or three stairs below. So the ways to reach a stair are the ways to reach each of those three stairs, added together.

The ground still has 1 way (you're already there). Stairs "below the ground" have 0 ways, because you can't start underground. That little rule saves you from special cases at the bottom.

More kinds of move, more terms: add up every stair you could have come from.

Below the ground: counts as 0 ways, so the edges take care of themselves.

Steps of 1, 2 or 3 · ways(n) = ways(n − 1) + ways(n − 2) + ways(n − 3)

01234

ways

a: 0
b: 0
c: 1

ways(0) = 1: standing on the ground, there's one way (do nothing). Stairs below 0 count as 0.

Move 1 of 5

You only need to remember three numbers

Look at what the table actually uses: each new answer reads only the three answers right before it. Everything older is never looked at again.

So instead of a whole table, keep three running numbers, like a window showing just the last three stairs. Work out the next answer, then slide the window up by one. It uses the same tiny bit of memory whether there are 4 stairs or 4 million.

Keep only what you'll read again: three numbers, not a whole table.

In code

# last three stairs: below, below, ground
a, b, c = 0, 0, 1
for _ in range(n):
    a, b, c = b, c, a + b + c
return c