Climbing Stair /*
Using Recursion:- Time Complexity:-(2^N)
Space Complexity:- O(N) class Solution {
public int climbStairs(int n) {
if(n<=1){
return 1;
}
int left=climbStairs(n-1);
int right=climbStairs(n-2);
return left+right;
}
} */ /*
Memoization:-(Top-Down) Time Complexity:- O(N)
Space Complexity:- O(N)->Array + O(N)-> recursion stack class Solution {
public int memo(int n,int [] dp){
if(n<=1) return 1;
if(dp[n]>0){
return dp[n];
}
int left=memo(n-1,dp);
int right=memo(n-2,dp);
dp[n]=left+right;
return dp[n];
}
public int climbStairs(int n) {
int dp[]=new int[n+1];
return memo(n,dp);
}
}
