Code Logo

Ways to Climb Stairs

Published at05 Jan 2026
Created by
Easy 6 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 1s and 2s 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
Recommendation Algorithm Flow for Ways to Climb Stairs

Solution Approach

A clean way to solve this is with dynamic programming. To reach step n, the last move must have been either a 1-step jump from n - 1 or a 2-step jump from n - 2.

That gives a very natural recurrence:

ways(n) = ways(n - 1) + ways(n - 2)

Every path to n - 1 can be extended by one 1-step move, and every path to n - 2 can be extended by one 2-step move. Those are exactly all valid ways to arrive at n.

The base cases are small and easy:

ways(1) = 1;
ways(2) = 2;

From there, we can build the answer iteratively:

let prevTwo = 1;
let prevOne = 2;

for (let step = 3; step <= n; step++) {
  const current = prevOne + prevTwo;
  prevTwo = prevOne;
  prevOne = current;
}

This avoids recursion and keeps only the last two values, since that is all we need.

If n is 1 or 2, we return the base value directly. Otherwise, after the loop, prevOne is the number of ways to reach step n. The time complexity is O(n), and the extra 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;
    }
}