Code Logo

Ways to Climb Stairs

Published at05 Jan 2026
Created by
Array Manipulation Easy 18 views
Like7

This problem asks how many different ways there are to reach the top of a staircase with exactly n steps when every move can be either 1 step or 2 steps.

What matters here is the order of the moves. For example, taking 1 then 2 is different from taking 2 then 1, because they are different sequences. So we are not just checking whether a total is possible. We are counting every valid sequence that adds up to n.

If n = 3, the answer is 3 because the valid sequences are [1,1,1], [1,2], and [2,1]. If n = 5, the answer is 8. As n gets larger, the number of valid sequences grows quickly.

So the task is to count all distinct step sequences made of 1 s and 2 s whose total length is exactly n.

Example Input & Output

Example 1
Input
n = 3
Output
3
Explanation

The sequences are [1,1,1], [1,2], and [2,1].

Example 2
Input
n = 5
Output
8
Explanation

There are eight distinct sequences of 1s and 2s that sum to 5.

Example 3
Input
n = 1
Output
1
Explanation

Only one way: take a single step.

Algorithm Flow

Recommendation Algorithm Flow for Ways to Climb Stairs

Solution Approach

Count the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. This is the Fibonacci sequence: ways(n) = ways(n-1) + ways(n-2), with ways(1)=1, ways(2)=2. Use rolling variables to compute iteratively.

function climbStairs(n) {
  if (n <= 2) return n;
  var a = 1, b = 2;
  for (var i = 3; i <= n; i++) {
    var c = a + b;
    a = b; b = c;
  }
  return b;
}

Each step can be reached from either one step below or two steps below, so the number of ways to reach step i is the sum of ways to reach i-1 and i-2.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int climb_stairs(Object n) {
        int num = (int) n;
        if (num <= 2) {
            return num;
        }
        int prev = 1;
        int curr = 2;
        for (int i = 3; i <= num; i++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}