C++解决最小花费爬楼梯问题（爬楼梯升级版）

问题描述

问题分析

这个题像极了0-1背包问题。实际上还是动态规划问题，从子问题来看，就是看走一步到达的阶梯所要求的体力花费和走两步到达的阶梯所要求的体力花费哪一个更小，总的来看就是看这些子问题的和哪个更小（0-1背包则是看哪个更大）。简单来说就是在这种可以分解成子问题的问题中，如果所有子问题都是最优解，那么这个问题的解就是最优的。理解了这个问题，代码就比较容易实现了。

问题解决（代码）

class Solution 
{
public:
    int minCostClimbingStairs(vector<int> &cost)
    {
        int length = cost.size();
        vector<int> sum(length);//创建存储总体力花费的数组
        sum[0] = cost[0];//题目中说0/1为初始阶梯，单独列出
        sum[1] = cost[1];
        for (int i = 2; i < length; i++)
        {//sum[n]表示上到第n层台阶需要花费的总体力
            sum[i] = min(sum[i - 1], sum[i - 2]) + cost[i];//递归，表示到达i层花费的总体力等于来这一层用的花费和之前在第（n-1）层花费的体力的和
        }
        return min(sum[length - 1], sum[length - 2]);
    }

};

因为这个题提交的时候并不是最优的方法，运行时间比较长，所以如果有更好的方法可以私信我，我们一起讨论。