🎨 Try our Free AI Image Generation Feature

70. Climbing Stairs

avatar
Dare2Solve

11 months ago

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];
};