Leetcode算法初学——动态规划算法“使用最小花费爬楼梯”

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode算法初学——动态规划算法“使用最小花费爬楼梯”，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1491字，纯文字阅读大概需要3分钟。

内容图文

题目：

数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。(难度：简单)

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
 示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

题解：

不同于简单的爬楼梯默认每阶楼梯花费体力都是1，本题爬到每阶楼梯的体力花费是不一样的，这道题我觉得难点就在于理解题意，特别是最后一句其实很容易忽略，“您需要找到达到楼层顶部的最低花费”，所以本题不是说检索到cost[n-1]后就结束了，而是要在cost[n-1]和cost[n-2]之间再做一次比较，因为还要再爬到楼顶。动态规划方程比较容易写出来，因为题目已经给了cost最小长度为2，所以不用再确定边界，直接将dp数组前两个赋值，自底向上，每次都是前面阶梯的最小值再加上新的阶梯就是走到那个阶梯的最小花费，f(x)=min(f(x-1),f(x-2))+cost[x]，本体难点就在于自底向上一定要判断到楼顶的花费。

代码：

 1 class Solution {
 2 public:
 3     int minCostClimbingStairs(vector<int>& cost) {
 4         int dp[1000];
 5         dp[0]=cost[0];
 6         dp[1]=cost[1];
 7         int n=cost.size();
 8         for(int i=2;i<n;i++)
 9         {
10             dp[i]=min(dp[i-1],dp[i-2])+cost[i];
11         }
12         return min(dp[n-1],dp[n-2]);
13     }
14 };

运行结果：

 

 该算法时间复杂度为O(n)。难度简单。

 

内容总结

以上是互联网集市为您收集整理的Leetcode算法初学——动态规划算法“使用最小花费爬楼梯”全部内容，希望文章能够帮你解决Leetcode算法初学——动态规划算法“使用最小花费爬楼梯”所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---