Climbing Stairs - LeetCodee

Problem Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Examples

Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    
    # Initialize first two numbers
    prev1, prev2 = 1, 2
    
    # Calculate Fibonacci sequence
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev1 = prev2
        prev2 = current
    
    return prev2

Java Solution


class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        // Initialize first two numbers
        int prev1 = 1;
        int prev2 = 2;
        
        // Calculate Fibonacci sequence
        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
        
        return prev2;
    }
}

C++ Solution


class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        // Initialize first two numbers
        int prev1 = 1;
        int prev2 = 2;
        
        // Calculate Fibonacci sequence
        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
        
        return prev2;
    }
};

JavaScript Solution


/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n <= 2) {
        return n;
    }
    
    // Initialize first two numbers
    let prev1 = 1;
    let prev2 = 2;
    
    // Calculate Fibonacci sequence
    for (let i = 3; i <= n; i++) {
        const current = prev1 + prev2;
        prev1 = prev2;
        prev2 = current;
    }
    
    return prev2;
};

C# Solution


public class Solution {
    public int ClimbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        // Initialize first two numbers
        int prev1 = 1;
        int prev2 = 2;
        
        // Calculate Fibonacci sequence
        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
        
        return prev2;
    }
}

Complexity Analysis

Time Complexity: O(n) to calculate n Fibonacci numbers
Space Complexity: O(1) using only constant extra space

Solution Explanation

This solution uses the Fibonacci sequence pattern:

Key insight:
- Ways to reach n steps = Ways to reach (n-1) + Ways to reach (n-2)
- This forms Fibonacci sequence
- Base cases: n=1 → 1 way, n=2 → 2 ways
Algorithm steps:
- Handle base cases (n ≤ 2)
- Initialize first two numbers:
  - prev1 = F(1) = 1
  - prev2 = F(2) = 2
- Calculate next numbers:
  - current = prev1 + prev2
  - Update previous numbers

Key points:

Dynamic programming approach
Optimized to O(1) space
Simple iterative solution
No recursion needed