70. Climbing Stairs Easy

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?

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

Approach

Input: There are n stairs.

Output: Each time you can climb 1 or 2 stairs, how many different ways are there to reach the top.

This problem belongs to Linear DP problems. Sometimes also called Fibonacci DP or 1D DP.

We can imagine that if there is only 1 step left, there will be only 1 way dp[1] = 1.

If there are only 2 steps left, there will be 2 ways dp[2] = 2.

If there are 3 steps left, that is 1 + 2 = 3 ways dp[3] = dp[1] + dp[2].

By extension, to know how many ways to climb n stairs, it is dp[n] = dp[n - 2] + dp[n - 1].

We can implement this using either recursion or a loop. Note that the recursive implementation needs to cache results to reduce redundant calculations and prevent stack overflow.

Implementation

python

class Solution:
    def climbStairs(self, n: int) -> int:
        # Special case handling: if the number of stairs <= 2, return n itself
        if n <= 2:
            return n

        # Method 1: Dynamic Programming (Bottom-Up)
        # Create an array of length n+1 to save the number of ways for each step
        dp = [0] * (n + 1)

        # Initialize the initial ways up to 2
        dp[1] = 1  # 1 step, only 1 way
        dp[2] = 2  # 2 steps, two ways: 1+1 or 2

        # Starting from step 3, number of ways = ways from 1 step below + ways from 2 steps below
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        # Returns answer evaluated to end
        return dp[n]

javascript

/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = function(n) {
    if (n <= 2) return n;

    const dp = Array(n + 1).fill(0);

    dp[1] = 1;
    dp[2] = 2;

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

    return dp[n];
};

python

from functools import cache

class Solution:
    def climbStairs(self, n: int) -> int:
        # Method 2: Memoized Recursion (Top-Down)
        # Use @cache to automatically cache calculated results, avoiding repetitive execution
        @cache
        def dp(i):
            # Base cases: if it's the 1st or 2nd step, the number of ways is simply i
            if i <= 2:
                return i

            # Otherwise, recursively calculate dp(i-1) and dp(i-2)
            return dp(i - 1) + dp(i - 2)

        # Call the memoized recursive function
        return dp(n)

javascript

/**
 * @param {number} n
 * @return {number}
 */
const climbStairsMem = function(n) {
    const cache = {};

    function dp(i) {
        if (i <= 2) return i;

        if (cache[i]) return cache[i];

        const res = dp(i - 1) + dp(i - 2);

        cache[i] = res;

        return cache[i];
    }

    return dp(n);
}

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

70. Climbing Stairs (English)

70. 爬楼梯 (Chinese)