Code Logo

Climbing Stairs

Published at24 Jul 2026
Created by
Easy 0 views
Like0

You are climbing a staircase that has n steps. Each time you can climb either 1 step or 2 steps. In how many distinct ways can you reach the top? This is one of the most fundamental dynamic programming problems and introduces the concept of overlapping subproblems.

To reach step i, you could have come from step i-1 (by taking 1 step) or from step i-2 (by taking 2 steps). Therefore, the number of ways to reach step i is the sum of the ways to reach the two previous steps: dp[i] = dp[i-1] + dp[i-2]. The base cases are dp[1] = 1 and dp[2] = 2.

This recurrence naturally leads to the Fibonacci sequence. An array of size n stores each subproblem result (O(n) space), but we can optimize to O(1) space using just two variables since each step only depends on the previous two. The time complexity is O(n).

Edge cases include n = 1 (only one way: take 1 step), n = 2 (two ways: 1+1 or 2), and n = 0 (0 ways, though the problem typically starts at n=1).

The climbing stairs recurrence produces the Fibonacci sequence shifted by one: F(1)=1, F(2)=2, F(3)=3, F(4)=5, F(5)=8. This sequence grows exponentially and illustrates how DP transforms exponential recursive trees into linear iterative computations.

Example Input & Output

Example 1
Input
1
Output
1
Explanation

Only one step: one way.

Example 2
Input
3
Output
3
Explanation

1+1+1, 1+2, 2+1. Three ways.

Example 3
Input
4
Output
5
Explanation

Five distinct combinations.

Example 4
Input
2
Output
2
Explanation

1+1 or 2. Two ways.

Example 5
Input
5
Output
8
Explanation

Eight ways for 5 steps.

Algorithm Flow

Recommendation Algorithm Flow for Climbing Stairs
Recommendation Algorithm Flow for Climbing Stairs

Solution Approach

DP with space optimization: use two variables for dp[i-1] and dp[i-2]. Update iteratively.

function solution(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;
}

Time O(n), Space O(1).

Best Answers

java
class Solution {
    public int solution(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}