day02|最小花费爬梯子

本文主要是介绍day02|最小花费爬梯子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最小花费爬梯子

比如 有一个数组 【2 5 20】我们直接选择从1号梯子（从零编号）跳两格就出去了。

算法原理

• 我们可以得出楼顶其实是数组的最后一个元素的下一个位置。
• 对于最值问题我们可以尝试使用dp
• dp我们首先应该定义状态方差的含义，一般以i元素结尾xxxx或者以i元素开始xxxx
• 对于这道题我们可以以i元素结尾的最小花费或者以i元素开始最小花费为状态方程
• 推状态方程就是找相邻状态的关系。

代码实现

一：到i位置结尾的最小花费dp[i]，

初始化：dp[0],dp[1] =0 因为我们最开始可以选择从0位置或者1位置开始爬台阶，到0或1位置的最小花费是0。返回dp[n] 是因为楼顶是n

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp ;dp.resize(n+1);dp[0] = 0;dp[1] = 0;for(int i = 2; i<=n;i++){dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
};

二从i位置起始最小花费

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp ;dp.resize(n+1);dp[n-1] = cost[n-1];dp[n-2] = cost[n-2];for(int i = n -3; i>=0;i--){dp[i] = min(dp[i+1] ,dp[i+2] ) + cost[i]; //支付cost[i]后 选择先后走一步或两步}return min(dp[0],dp[1]);}
};

这篇关于day02|最小花费爬梯子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---