class Solution {
public:
    int climbStairs(int n) 
    {
        int dp[n+1];
        for(int i=0;i<=n;i++)dp[i]=0;
        dp[0]=0;
        dp[1]=1;
        // dp[2]=2;
        if(n==1)return 1;
        if(n==2)
        {
            return 2;
        }
        dp[2]=2;
        
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<=2;j++)
            {
                dp[i]+= dp[i-j];
            }
        }
        return dp[n];
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        int dp[n+1];
        
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        for(int i=2;i<n;i++)
        {
            dp[i] = cost[i] + min(dp[i-1] , dp[i-2]);
        }
       return min(dp[n-1],dp[n-2]);
    }
};