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