算法题每日一练---第38天：爬楼梯的最少成本

一、问题描述

数组的每个下标作为一个阶梯，第 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 。

考察

动态规划中等题型
建议用时15~30min

三、问题分析

这也是一道比较典型的动态规划问题，动态规划没做过的可以看这一篇入门题解：

算法题每日一练---第34天： 青蛙跳台阶

还是用我们的三步走，老套路：

第一步 含义搞懂：

题目要求求出到达楼层顶部的最低花费，那我们动态规划的数组dp[i]就表示从下标0到达下标i的最小花费。

注意

这一题要求到达楼顶，所以虽然数组的下标到n-1，我们要求到n。

第二步 变量初始：

只需要初始化两个变量：

dp[0]=0;
dp[1]=0;

第三步 规律归纳：

假设i为2,那么dp[2]该如何利用前面两个dp关系呢？

0->2需要跳两步，花费dp[0]+cost[0]
1->2需要跳一步，花费dp[1]+cost[1]

dp[2]只能由上面的两个式子得到，我们选一个小的不就行了，那推广到dp[3]、dp[4]不也是一样。

所以dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

三步走，打完收工！

四、编码实现

classSolution {
public:
intminCostClimbingStairs(vector<int>&cost) {
inti,n=cost.size();//初始化intdp[n+2];
dp[0] =dp[1]=0;//变量初始for (i=2;i<=n;i++) 
    {
dp[i] =min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);//规律归纳    }
returndp[n];//输出结果    }
};

五、测试结果