Climbing Stairs
EasyPrompt
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 stepsExample 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
1 <= n <= 45
Approaches
5 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's recurrence relation, ways(n) = ways(n-1) + ways(n-2), into a recursive function. It's the most straightforward way to think about the problem but is highly inefficient.
Algorithm
- Define a function
climbStairs(n). - Handle the base cases: if
nis 1, return 1; ifnis 2, return 2. - For other values of
n, make a recursive call:return climbStairs(n - 1) + climbStairs(n - 2);.
Walkthrough
The core idea is that to reach the n-th step, you must have come from either the (n-1)-th step (by taking one step) or the (n-2)-th step (by taking two steps). The total number of ways is the sum of the ways to reach these two preceding steps. We define a function climbStairs(n) that calls itself for n-1 and n-2 and sums their results. The base cases are for n=1 (1 way) and n=2 (2 ways). This creates a large recursion tree where the number of ways for the same step is calculated multiple times, leading to an exponential time complexity.
public class Solution { public int climbStairs(int n) { if (n <= 0) { return 0; } if (n == 1) { return 1; } if (n == 2) { return 2; } return climbStairs(n - 1) + climbStairs(n - 2); }}Complexity
Time
O(2^n)
Space
O(n)
Trade-offs
Pros
Simple to write and understand as it directly models the problem's definition.
Cons
Extremely inefficient due to re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' error for moderately large values of
n(e.g., n > 35).
Solutions
Solution
class Solution {public int climbStairs(int n) { int a = 0, b = 1; for (int i = 0; i < n; ++i) { int c = a + b; a = b; b = c; } return b; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.