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```

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