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