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*

*List of all LeetCode Solution*

## Topics

Dynamic Programming

## Companies

Adobe, Apple

## Level of Question

Easy

**Climbing Stairs LeetCode Solution**

## Table of Contents

**Problem Statement**

You are climbing a staircase. It takes ** n** steps to reach the top. Each time you can either climb

**or**

*1***steps. In how many distinct ways can you climb to the top?**

*2*Example 1:Input: n = 2Output: 2Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 stepsExample 2:Input: n = 3Output: 3Explanation: 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.