题解 | 最小花费爬楼梯

#include <algorithm>
#include <climits>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        // write code here
        /*印象中做过这道题，从下标0开始，或者是从下标1开始，选择爬一个或者两个台阶。其实就是一个覆盖范围的问题，选择这个覆盖范围中落地点花费最小的？如果最后一步跳过了，没有落到平台上；或者直接跳到了平台上；这就是最后走的两步。
        **************
        如何找出递推关系呢，如果从自顶向下开始算起，要么从前一个台阶跳上来，要么从前前一个台阶跳上来，选择他们两个中花费最小的一个
        f（n）=min（fn-1，fn-2）；
		其实也可以迭代，可以看官解。但是注意这个自底向上的迭代并不是贪心，它是动态规划，它有比较这一步骤
        */
        int n=cost.size();
        vector<int> maxcost(n+1,INT_MAX);
        //maxcost[0]=cost[0];
        if(n==1)return cost[0]<cost[1]?cost[0]:cost[1];
        //有n个台阶。
        func(cost, n, maxcost);
        return maxcost[n];
    }
    int func(vector<int>& cost,int n,vector<int>& maxcost){
        
        if(maxcost[n]!=INT_MAX)return maxcost[n];
        if(n==0||n==1) return 0;//边界条件是什么样的呢
        //根据数据范围,这里n就是大于等于二的
        maxcost[n]=min(func(cost,n-1,maxcost)+cost[n-1], func(cost,n-2,maxcost)+cost[n-2]);//不算最后这个台阶的体力值
        return maxcost[n];
    }
};