DSA problem
Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top, and at each move you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?
This is the gateway problem for 1-D dynamic programming. To reach step i, your last move came either from step i - 1 (one-step hop) or from step i - 2 (two-step hop). So the number of ways to reach i is dp[i] = dp[i - 1] + dp[i - 2] — the Fibonacci recurrence in disguise.
With base cases dp[1] = 1 and dp[2] = 2, a straightforward tabulation in an array of length n + 1 works in O(n) time and O(n) space. But notice every dp[i] depends only on the previous two values, so we don't actually need the whole array.
The optimal approach keeps two rolling variables and updates them in lockstep. This gives O(n) time with O(1) space and is the canonical space-optimized 1-D DP. The exponential brute-force recursion that branches at every step is correct in spirit but takes O(2^n) time and is intractable for n near the upper bound.
Examples
n = 22n = 33n = 45Constraints
- 1 <= n <= 45
- You can take exactly 1 or 2 steps at a time.
- The answer fits in a 32-bit signed integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.