Climbing Stairs
Problem
You climb a staircase of n steps, taking 1 or 2 steps at a time. Return the number of distinct ways to reach the top.
Example 1
Input: n = 3 Output: 3
1+1+1, 1+2, 2+1.
Test cases
Case 1
Input: 2 Expected: 2
Case 2
Input: 3 Expected: 3
Case 3
Input: 5 Expected: 8
View solutionHide solution1 approach
1. Two rolling variables
Time O(n)Space O(1)
ways(i) = ways(i − 1) + ways(i − 2): the last step was 1 or 2. It is Fibonacci.
function climbStairs(n) { let a = 1, b = 1; // ways(0), ways(1) for (let i = 2; i <= n; i++) [a, b] = [b, a + b]; return b;}