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

本文主要是介绍C++解决最小花费爬楼梯问题（爬楼梯升级版），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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]);
    }

};

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

这篇关于C++解决最小花费爬楼梯问题（爬楼梯升级版）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！