Q-1 Climbing Stairs - LeetCode 70
Sat Sep 09 2023 14:45:10 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int climbStairs(int n) {
// return s(n , new Integer[n+1]);
//Tabulization 2*n Sc - n
int []dp = new int[n+1];
dp[0] = 1;
for(int i = 1 ;i <= n ;i++){
int one = 0 , two = 0;
if(i-1 >= 0 )
one = dp[i-1];
if(i-2 >= 0)
two = dp[i-2];
dp[i] = one+two;
}
return dp[n];
}
//recursive 2^n + memo 2*n Sc- n(stack height) + n (dp array)
public int s( int n , Integer[] dp){
if(n == 0)
return 1;
if(dp[n] != null)
return dp[n];
int one = 0 , two = 0;
if(n-1 >= 0 )
one = s(n-1 , dp);
if(n-2 >= 0)
two = s(n-2 , dp);
return dp[n] = one+two;
}
}
content_copyCOPY
https://leetcode.com/problems/climbing-stairs/
Comments