Climbing Stairs
Problem statement
A staircase has n steps. Each move you climb either 1 step or 2 steps. Return how many different sequences of moves take you from the bottom to exactly the top.
Order matters: climbing 1 then 2 is a different sequence from 2 then 1. n is at least 1.
This is the usual first dynamic-programming problem, because the answer for n is built directly from the answers for smaller staircases.
Examples
Example 1
Input: n = 5
Output: 8
Explanation: For example 1+1+1+1+1, 2+2+1, 2+1+2 and 1+2+2 are four of the eight sequences.
Example 2
Input: n = 1
Output: 1
Explanation: The only option is a single 1-step move.
Hints
Approach
Bottom-up with two variables. Build from the bottom: prev and cur hold ways(k - 1) and ways(k). Each step shifts them forward with prev, cur = cur, prev + cur. After n - 1 steps starting from ways(0) = ways(1) = 1, cur is the answer. These are the Fibonacci numbers shifted by one.
O(n)Space O(1)def climb_stairs(n): prev, cur = 1, 1 # ways(0), ways(1) for _ in range(n - 1): prev, cur = cur, prev + cur return cur print(climb_stairs(5))print(climb_stairs(1))Follow-up questions
- Moves can be any size in a list
steps, for example[1, 3, 5]. (Sum over the last move; this becomes a coin-change-style count.) - Some steps are broken and can't be landed on. How does the recurrence change?
Frequently asked questions
It is the entry point to dynamic programming, and loops that include DP usually warm up with it or with House Robber. The skill it checks is general: spot that a brute-force recursion repeats work, then cache it or build the answer bottom-up. The same move turns a slow recursive dependency walk into a fast one.
It means there is exactly one way to cover zero remaining steps: do nothing. Setting it to 1 makes the recurrence give ways(2) = ways(1) + ways(0) = 2, which is correct (1+1 or 2).
Yes. Fibonacci numbers can be computed in O(log n) with matrix exponentiation or the fast-doubling identities. It rarely matters here, because the values overflow 32-bit integers around n = 45 anyway.