class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //dp[i]表示爬到第i阶楼梯需要的最小花费
        vector<int> dp(cost.size() + 1, 0); 
        for(int i = 2; i <= cost.size(); i++)
            //每次选取最小的方案
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); 
        return dp[cost.size()];
    }
};


// #include <cmath>
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
//      *
//      *
//      * @param cost int整型vector
//      * @return int整型
//      */
//     int ans=INT_MAX;

//     void dfs(vector<int>& cost, int n, int index, int sum)
//     {
        
//         if(index==n)
//         {
//             ans = min(ans,sum);
//             return;
//         }

//         sum += cost[index];

//         if(index+1<=n)
//             dfs(cost, n, index+1, sum);

//         if(index+2<=n)
//             dfs(cost, n, index+2, sum);
//     }

//     int minCostClimbingStairs(vector<int>& cost) {
//         // write code here
//         // 深度优先搜索
//         int n = cost.size();
        
//         dfs(cost,n,0,0);
//         dfs(cost,n,1,0);
//         return ans;
//     }
// };