2.md

Climbing Staris

Method 1 (Tradational way-> Recusrion) //TLE

int climbStairs(int n) {
        
        if(n==0)
            return 1;
        if(n==1)
            return 1;

        int step1=climbStairs(n-1);
        int step2=climbStairs(n-2);

        return step1 + step2;    
    }

Memorization (TC-O(n) and SC-O(n))

 int ans(int n,vector<int>&dp)
    {
         if(n==0)
            return 1;
        if(n==1)
            return 1;

        if(dp[n]!=-1)
            return dp[n];    

        int step1=ans(n-1,dp);
        int step2=ans(n-2,dp);

        return dp[n]=step1 + step2;    
    }
    
   
    int climbStairs(int n) {
         vector<int> dp(n+1,-1);
         return ans(n,dp);
    }   

Tabulation (TC- 0(n) AND SC - O(1))

 int climbStairs(int n) {
           if(n<=3)
            return n;
   int  prev2=2;
    int prev=3;
    int cur;
    for(int i=4;i<=n;i++)
    {
        cur= prev2 +prev;
        prev2=prev;
        prev=cur;
    }
    return prev;
    }