Climbing Stairs — Fibonacci DP

Problem

Count distinct ways to climb n stairs, taking 1 or 2 steps at a time.

Example: n=3 → 3 (1+1+1, 1+2, 2+1)

Approach — Space-Optimized Fibonacci

dp[i] = dp[i-1] + dp[i-2]. Only need last two values.

Time: O(n) | Space: O(1)

Solutions

C

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

C++

class Solution {
public:
    int climbStairs(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;
    }
};

Java

class Solution {
    public int climbStairs(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;
    }
}

JavaScript

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

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n<=2: return n
        a,b=1,2
        for _ in range(3,n+1): a,b=b,a+b
        return b

Complexity

Time: O(n) | Space: O(1)