最小代价爬楼梯题目链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs数组的每个下标作为一个steps，第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。提示：cost的长度范围为[2,1000]。cost[i]将是一个整数数据，范围是[0,999]。思考的题目可以说是昨天的动态规划：爬楼梯的成本版。注意标题说明：每爬一个梯子，都要花费相应的体力值。一旦你支付了相应的体力值，你就可以选择爬一个梯子或者爬两个梯子。所以在示例1中，只花费了一个15。可以走到梯子的最顶端，最后一步可以理解为不花钱。看完题大家应该都知道，需要指定的动态规划，贪心是不可能的。判断dp数组和下标的意义使用动态规划，需要一个数组来记录状态。这道题只需要一个一维数组dp[i]。dp[i]的定义：到达第i步所需的最小体力为dp[i]。（这里注意，第一步一定要花）对于dp数组的定义，大家想必都清楚了吧！确定递归公式得到dp[i]的方法有两种，一种是dp[i-1]，一种是dp[i-2]。那么你应该选择dp[i-1]还是dp[i-2]？它必须是最小的，所以dp[i]=min(dp[i-1],dp[i-2])+cost[i];注意这里为什么要加上cost[i]，而不是cost[i-1]、cost[i-2]，因为题目说的是：每爬一个梯子，就要花费对应的dp的定义数组，dp数组的初始化其实是比较难的，因为不可能用最少的体力去初始化第i步。然后看递推公式，dp[i]由dp[i-1],dp[i-2]导出，由于不可能初始化所有dp[i]，那么只初始化dp[0]和dp[1]就够了，其他的最终由dp[0]dp[1]发起。所以初始化代码为：vectordp(cost.size());dp[0]=cost[0];dp[1]=cost[1];确定遍历顺序的最后一步，递归公式有了，初始化有了，怎么遍历？这道题的遍历顺序其实比较简单，简单到很多同学都忽略了思考的这一步，直接写代码。因为是模拟步，dp[i]是由dp[i-1]dp[i-2]发起的，所以从前到后遍历cost数组就可以了。但是对于稍微难一点的动态规划来说，它的遍历顺序就不好确定了。比如：01背包，我们都知道有两个for循环，一个遍历物品嵌套一个遍历背包容量，那为什么不用一个遍历背包容量嵌套一个遍历物品呢？而在使用一维dp数组的时候遍历为什么背包容量需要倒转呢？这些都与遍历顺序密切相关。当然，背包问题的后续《代码随机记录》会重点讲解！实例推导dp数组以实例2：cost=[1,100,1,1,1,100,1,1,100,1]来模拟dp数组的状态变化如下：使用最小代价爬楼梯。如果写代码有问题，把dp数组打印出来，看看是不是和上面的推导一样。以上分析完成后，整体C++代码如下：//Version1classSolution{public:intminCostClimbingStairs(vector&cost){vectordp(cost.size());dp[0]=成本[0];dp[1]=成本[1];for(inti=2;i&cost){intdp0=cost[0];intdp1=cost[1];for(inti=2;i&cost){vectordp(cost.size()+1);dp[0]=0;//默认step是no物理成本dp[1]=0;for(inti=2;i<=cost.size();i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}returndp[cost.size()];}};这样写看起来比较流畅，就是和标题描述不符。呵呵，没必要深究题意这么详细。大家只要知道，题意就是第一步没花，或者最后一步没花，都可以。总结一下，可以发现这个题目比昨天的动态规划：爬楼梯要难一些，但是整体思路是一样的。从动态规划：斐波那契数列到动态规划：爬楼梯到今天的话题，记录者感受渐变。每个系列开始的时候，有的录音师跟我说题目太简单了，要赶紧升难度，但是有的录音师跟我说有点难，我跟不上。其实我选的题都是有目的性的，哪怕是简单的题，也是为了练习方法论，然后逐渐增加难度，一个环节接一个环节。但是我也可以选一个有难度的问题来讲，其实是最省事的。我不在意话题的先后顺序，随便找一个，随心情说说。难的是按照梯度，一步一步来安排题目，然后按照统一的方法论把它们串起来，哈哈，所以不要催我，跟着我的节奏一步步来就好了。学算法，找《CodeCaprice》，没问题！其他语言版本JavaclassSolution{publicintminCostClimbingStairs(int[]cost){if(cost==null||cost.length==0){return0;}if(cost.length==1){returncost[0];}int[]dp=newint[cost.length];dp[0]=cost[0];dp[1]=cost[1];for(inti=2;iint:dp=[0]*(len(cost))dp[0]=cost[0]dp[1]=cost[1]foriinrange(2,len(cost)):dp[i]=min(dp[i-1],dp[i-2])+cost[i]returnmin(dp[len(cost)-1],dp[len(cost)-2])GofuncminCostClimbingStairs(cost[]int)int{dp:=make([]int,len(成本))dp[0],dp[1]=成本[0],成本[1]fori:=2;i
