Problem
You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?
Example
Input: n = 2
Output: 2
Either 1+1 or 2.Input: n = 3
Output: 3
1+1+1, 1+2, 2+1.Solution
This is Fibonacci in disguise. ways(n) = ways(n-1) + ways(n-2). Use iterative bottom-up to save memory.
def climb_stairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return bfunction climbStairs(n) {
if (n <= 2) return n;
let a = 1, b = 2;
for (let i = 3; i <= n; i++) {
[a, b] = [b, a + b];
}
return b;
}int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int next = a + b;
a = b;
b = next;
}
return b;
}public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int next = a + b;
a = b;
b = next;
}
return b;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
To reach step n, you either took 1 step from n-1 or 2 steps from n-2. So ways(n) = ways(n-1) + ways(n-2). Same recurrence as Fibonacci.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?