题解 | 最小花费爬楼梯

#include <cstddef>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    //cost数组的大小就是多少个台阶
    //第i阶楼梯依赖于前面爬i-1阶台阶的最低花费
    //可以转化为子问题，并且子问题会被多次计算
    //典型的递归，并且可以通过自底向上来实现
    int minCostClimbingStairs(vector<int>& cost) {
        // write code here
         int n=cost.size();
         if(n==1)//当仅有一阶楼梯或两阶楼梯时，可以选择从下标为0的台阶爬两个台阶或者从下标为1的楼梯爬一个台阶
         {
            return cost[0];
         }
         int cost0=cost[0];
         int cost1=cost[1];
         int mincost0=0;
         int mincost1=0;
         int cur;
         //当i=1时，说明有两个楼梯，可以选择一次爬两个
         for(int i=2;i<=n;i++)
         {
            cur=min(cost[i-2]+mincost0,cost[i-1]+mincost1);
            mincost0=mincost1;
            mincost1=cur;
         }
       return cur;
    }
};