70. Climbing Stairs

Description

The problem is to determine the number of distinct ways to climb a staircase with n steps, where you can either take 1 step or 2 steps at a time.

Intuition

The number of ways to reach a particular step is the sum of the ways to reach the previous step and the step before that. This is because to reach a step i, you can come from step i-1 with a single step or from step i-2 with a two-step jump. This forms the basis of a dynamic programming solution.

Approach

1. Base Cases: - If n is 0 or 1, there's only one way to climb the stairs, which is doing nothing or taking a single step.
2. Dynamic Programming Array: - Create an array dp where dp[i] represents the number of ways to reach step i. - Initialize dp[0] and dp[1] to 1.
3. Iterate and Fill: - For each step from 2 to n, set dp[i] to the sum of dp[i-1] and dp[i-2] because you can either come from the previous step or the step before that.
4. Result: - The value at dp[n] will be the number of ways to reach the nth step.

Complexity

Time Complexity:

O(n), since we are iterating from 2 to n to fill the dp array.

Space Complexity:

O(n), due to the dp array that stores the number of ways to reach each step up to n.

Code

C++

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        vector dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;

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

        return dp[n];
    }
};

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1

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

Java

class Solution {
    public int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

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

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

        return dp[n];
    }
}

JavaScript

var climbStairs = function (n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;

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

    return dp[n];
};