Climbing Stairs Problem Solution

Climbing Stairs Problem: 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 :

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Climbing Stairs Problem Solution

Problem Solution In Python

def climbStairs(self, n: int) -> int:
        def dp(n, cache):
            if n not in cache:
                cache[n] = dp(n-1, cache) + dp(n-2, cache)
            return cache[n]
        return dp(n, {1: 1, 2: 2})

Problem Solution In Java

class Solution {    
    int [] cache = new int[46];    
    public int climbStairs(int n) {  
        if(n < 0) return 0;
        if(n == 0) return 1;        
        int val = cache[n];        
        if(val != 0)
            return val;        
        val = climbStairs(n - 1) + climbStairs(n - 2);       
        cache[n] = val;        
        return val;
    }
}

Problem Solution In C++

class Solution {
public:
    int climbStairs(int n) {
        vector<int>dp;
        dp.resize(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];
    }
};

Problem Solution In C

int climbStairs(int n){
    int* a = (int*)malloc(sizeof(int)*2);
    
    a[0] = 1;
    a[1] = 1;
    
    for (int i=2;i<=n;i++){
        a[i%2] =  a[0] + a[1];
    }
    return a[n%2];
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment