Climbing Stairs LeetCode Solution

Last updated on October 10th, 2024 at 02:01 am

Here, We see Climbing Stairs LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Dynamic Programming

Companies

Adobe, Apple

Level of Question

Easy

Climbing Stairs LeetCode Solution

Climbing Stairs LeetCode Solution

Problem Statement

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

1. Climbing Stairs Leetcode Solution C++

class Solution {
public:
    int dp[46];
    int climbStairs(int n) {
        if(dp[n]!=0) return dp[n];
  
        if(n==1 || n==2) return n;
        dp[n]=climbStairs(n-1)+climbStairs(n-2);
        return dp[n];
    }
};

1.1 Explanation

  • Memoization Array Initialization: An array dp of size 46 is initialized to store the results of subproblems. The size 46 is chosen because it is assumed that n will not exceed 45.
  • Check Memoized Value: If the result for n is already computed and stored in dp[n], return that value.
  • Base Cases: If n is 1 or 2, return n directly because there is only one way to climb 1 step and two ways to climb 2 steps.
  • Recursive Computation with Memoization: Compute the result for n by recursively calling climbStairs(n – 1) and climbStairs(n – 2) and store the result in dp[n].

1.2 Time Complexity

  • O(n) due to memoization.

1.3 Space Complexity

  • O(n) due to the recursion stack and the dp array.

2. Climbing Stairs Leetcode Solution Java

class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n == 1 || n == 2){return n;}
    int[] mem = new int[n];
    mem[0] = 1;
    mem[1] = 2;
    for(int i = 2; i < n; i++){
        mem[i] = mem[i-1] + mem[i-2];
    }
    return mem[n-1];
    }
}

2.1 Explanation

  • Base Cases: If n is 0, 1, or 2, return n directly because there are no stairs to climb, one way to climb 1 step, and two ways to climb 2 steps.
  • Memoization Array Initialization: Initialize an array mem of size n to store the results of subproblems. Set mem[0] to 1 and mem[1] to 2.
  • Iterative Computation: Fill the mem array iteratively using the relation mem[i] = mem[i – 1] + mem[i – 2].
  • Return Result: Return the value mem[n – 1], which contains the number of ways to climb n steps.

2.2 Time Complexity

  • O(n) due to the single loop that iterates n times.

2.3 Space Complexity

  • O(n) due to the mem array.

3. Climbing Stairs Leetcode Solution JavaScript

var climbStairs = function(n) {
    let prev = 0;
    let curr = 1;
    let tmp;
    for(let i = 1; i <= n; i++){
         tmp = prev;
        prev = curr;
      curr += tmp;
   }
   return curr;
};

3.1 Explanation

  • Initialize Variables: Initialize prev to 0 and curr to 1. These variables will store the number of ways to climb the previous two steps.
  • Iterative Computation: Iterate from 1 to n, updating prev and curr to reflect the number of ways to climb the current step. tmp temporarily holds the value of prev.
  • Return Result: Return curr, which contains the number of ways to climb n steps.

3.2 Time Complexity

  • O(n) due to the single loop that iterates n times.

3.3 Space Complexity

  • O(1) because only a constant amount of extra space is used.

4. Climbing Stairs Leetcode Solution Python

class Solution(object):
    def climbStairs(self, n):
        a, b = 1, 1
        for i in range(n):
            a, b = b, a + b
        return a

4.1 Explanation

  • Initialize Variables: Initialize a and b to 1. These variables will store the number of ways to climb the previous two steps.
  • Iterative Computation: Iterate from 0 to n-1, updating a and b to reflect the number of ways to climb the current step.
  • Return Result: Return a, which contains the number of ways to climb n steps.

4.2 Time Complexity

  • O(n) due to the single loop that iterates n times.

4.3 Space Complexity

  • O(1) because only a constant amount of extra space is used.
Scroll to Top