Climbing Stairs
A charity stair-climb takes place in a stadium stairwell with n steps. With each stride a climber goes up either one or two steps, and the organizers want to know how many different stride patterns lead from the ground to exactly the top step.
Return the number of distinct sequences of one-step and two-step strides that add up to n. Two sequences count as different when they differ at any position, so 1 + 2 and 2 + 1 are both counted.
Input: n = 4 Output: 5
Explanation: The patterns are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Input: n = 6 Output: 13
Input: n = 1 Output: 1
Explanation: A single one-step stride is the only option.
Constraints
nis between 1 and 45.
Follow-up: Can you get it in O(log n) time? (Hint: the recurrence can be written as a 2×2 matrix power.)
💡 Hint 1
Think about the very last move. It was either a 1-step from step n - 1 or a 2-step from step n - 2.
💡 Hint 2
So ways(n) = ways(n - 1) + ways(n - 2). Computing this recursively without caching repeats a lot of work.
💡 Hint 3
You only ever need the previous two values, so two variables are enough.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Every way to reach step n ends with either a 1-step (from n - 1) or a 2-step (from n - 2), and those two groups never overlap, so ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1. That is the Fibonacci recurrence. Build it bottom-up while keeping only the last two values.
function climbStairs(n) {
let prev = 1; // ways(i - 1)
let curr = 1; // ways(i)
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}class Solution {
public int climbStairs(int n) {
int prev = 1, curr = 1;
for (int i = 2; i <= n; i++) {
int next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number} n
* @return {number}
*/
function climbStairs(n) {
}Run your code to see results here.