Climbing Stairs

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}