One, two or three steps at a time
The recurrence now looks back three steps instead of two; keep only the last three values, not a whole array. About 10 minutes.
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.
- 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.
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.
# 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 cEach answer adds up the three answers just before it. How many numbers do you need to keep as you walk up the stairs?
- A3
- B1
- CAll of them
Show the answer
3. Exactly the three the next answer reads. Anything older is never used again.
One, two or three steps at a time
A staircase has n stairs. From any stair, you can move up by 1, 2 or 3. Return the number of distinct ways to go from the ground (stair 0) to stair n.
n = 4 → 7
0 ≤ n ≤ 48