The problem
A staircase has n steps. Each move climbs one step or two. Return the number of different ways to reach the top.
Examples
01
- Input
n = 2
- Output
2
02
- Input
n = 3
- Output
3
Constraints
- 1 ≤ n ≤ 45
The idea
Look at the last move. It either came from step n − 1 (one step) or from step n − 2 (two). Every route is one or the other, never both, so ways(n) = ways(n − 1) + ways(n − 2). With ways(0) = 1 and ways(1) = 1, this is the Fibonacci sequence.
Computing that by recursion alone repeats the same values over and over — exponentially many calls. Dynamic programming computes each value once, smallest first; and since each needs only the two before it, two variables are enough. For n = 5: 1, 1, 2, 3, 5, 8.
- Time
- O(n)
- Space
- O(1) — two numbers
Solution · every language run against every case
class Solution: def climbStairs(self, n: int) -> int: # ways(i) = ways(i - 1) + ways(i - 2): the last move was one step or two. a, b = 1, 1 # ways to reach step 0 and step 1 for _ in range(n - 1): a, b = b, a + b return b