Difficulty: Easy · LeetCode 70

Problem

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you climb to the top?

Understanding the problem

At every step, you can climb either 1 or 2 stairs. To reach step n, you come from n-1 or n-2.

Intuition

Subproblem overlap means dp[i] = dp[i-1] + dp[i-2]. We can build bottom-up or optimize space to only 2 variables.

Approach

Check base cases: if n <= 2, return n.
Maintain prev2 = 1 and prev1 = 2.
Loop from 3 to n updating current = prev1 + prev2, shifting prev2 = prev1 and prev1 = current.
Return prev1.

Naive Solution — Recursion

Generate every climb step combination by recursively deciding whether to take 1 or 2 steps.

Python

class Solution:
    def climbStairs(self, n):
        def dfs(step):
            if step == n:
                return 1

            if step > n:
                return 0

            return dfs(step + 1) + dfs(step + 2)

        return dfs(0)

C++

class Solution {
public:
    int climbStairs(int n) {
        return dfs(0, n);
    }

private:
    int dfs(int step, int n) {
        if (step == n) return 1;
        if (step > n) return 0;
        return dfs(step + 1, n) + dfs(step + 2, n);
    }
};

Java

class Solution {
    public int climbStairs(int n) {
        return dfs(0, n);
    }

    private int dfs(int step, int n) {
        if (step == n) return 1;
        if (step > n) return 0;
        return dfs(step + 1, n) + dfs(step + 2, n);
    }
}

JavaScript

var climbStairs = function(n) {
    const dfs = (step) => {
        if (step === n) return 1;
        if (step > n) return 0;
        return dfs(step + 1) + dfs(step + 2);
    };

    return dfs(0);
};

Time: O(2^n) · Aux Space: O(n)

Optimized Code (Python 3)

Python

class Solution:
    def climbStairs(self, n):
        if n <= 2:
            return n

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

C++

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;

        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
};

Java

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

JavaScript

var climbStairs = function(n) {
    if (n <= 2) return n;

    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
};

Time: O(n) · Space: O(1) (Space Optimized) / O(n) (DP Array)

Takeaway

Previous 2 states DP — Each state only depends on the immediate two previous states.