A staircase has n steps. Each move takes you up either one step or two steps.
Return how many different sequences of moves take you from the bottom to exactly the top step.
Sequences that differ at any move count separately, so 1 + 2 and 2 + 1 are two ways.
Example 1
- Input
- n = 3
- Output
- 3
1 + 1 + 1, 1 + 2 and 2 + 1.Example 2
- Input
- n = 4
- Output
- 5
1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1 and 2 + 2.Constraints
- 1 ≤
n≤ 45
Show the pattern
Dynamic programming (1D)
Your last move onto step n came from step n − 1 or from step n − 2, so the count for n is the sum of the counts for the two steps below it: the small answers build the big one.
See dynamic programming (1d) in a visualiserShow the approach
Let ways(k) be the number of ways to reach step k. The last move onto step k is either a single
step from k − 1 or a double step from k − 2. Those two groups of sequences never overlap, so
ways(k) = ways(k − 1) + ways(k − 2), starting from ways(0) = 1 (standing at the bottom is one
way) and ways(1) = 1.
Work upwards from the bottom. Each answer needs only the two before it, so two variables are enough. The answers are the Fibonacci numbers, shifted along by one.
Time: O(n) · Space: O(1)