746.使用最小花费爬楼梯

746.使用最小花费爬楼梯#

题目链接

题目说每个楼梯都千奇百怪，有的楼梯从上面迈步很简单，有的则很难，不同的楼梯迈步的难度我们将其抽象成费用，费用高的就难，低的就简单，我们的目的就是找到最简单的路线

题目会给出一个长度至少为2的列表cost，下例

1
cost = [1,100,1,1,100]

我们一次可以迈出一步或两步，比如说我们在第i阶楼梯，我们就可以走到第i+1阶或者第i+2阶上，那我们就想了是不是我们只要找两个之中花费最小的走就行了呢？让我们试试

第1个楼梯花费1，第2个楼梯花费100，第1个小，所以跳到第1个上，开始没有花费 花费+0 总花费0 开始->[0]

第2个楼梯花费100，第3个楼梯花费1，第3个小，所以跳到第3个上，第2个楼梯的花费是1 花费+1 总花费1 [0]->[2]

第4个楼梯花费1，第5个楼梯花费100，第4个小，所以跳到第4个上，第3个楼梯的花费是1 花费+1 总花费2 [2]->[3]

第5个楼梯花费1，跳2阶可以直接到终点，所以跳到终点上，第4个楼梯的花费是1 花费+1 总花费3 [3]->终点

在脑内仔细一验算发现还真是最小花费，直接提交

然后发现没通过，看下输入发现两个选最小并不能适应所用场景，比如在下面

1
cost=[10,15,20]

这里如果我们迈向10，那么就掉进陷阱了，因为直接到15才是最优的

那我们应该怎么办？

思考一下我们想到，其实这就是之前问题的翻版，之前我们输出1楼梯的种类加到2楼梯上，输出2楼梯的种类加到3楼梯上…直到算出n楼梯的数量

我们不直接求整体，而是先求部分，再从部分算出整体

我们这里也可以运用这样的思想，我们的目标是到顶，我们把数组长度称为n吧，那么我们的目标就是到n+1，到 n+1有几种路可以走呢

(虽然数组从0开始，但为了方便，我们就姑且认为下面的数组从1开始吧)

1. 从n迈一步到n+1 花费cost[n] + 迈上n的最优花费
2. 从n-1迈两步到n+1 花费cost[n-1] + 迈上n-1的最优花费

那么迈上n和n-1的花费怎么算呢

1. 从n-1迈一步到n 花费cost[n-1] + 迈上n-1的最优花费
2. 从n-2迈两步到n 花费cost[n-2] + 迈上n-2的最优花费

n的花费就是上面两个中最小的

1. 从n-2迈一步到n-1 花费cost[n-2] + 迈上n-2的最优花费
2. 从n-3迈两步到n-1 花费cost[n-3] + 迈上n-3的最优花费

n-1的花费就是上面两个中最小的

观察上面算式，我们发现n的最优花费总是为

1
#用M[n]来表示n的最优花费
2
M[n] = min(cost[n-1]+M[n-1] , cost[n-2]+M[n-1])
3
#min表示两个中取最小

我们继续推导，为了知道n-1的最优花费，我们得先知道n-2和n-3的，为了知道n-2…

最后，为了知道3的最优花费，我们得知道1和2最优花费，由于我们可以直接跳上1和2，所以1和2的最优花费为0，即

1
M[1]=0;M[2]=0;

之后我们就可以算出爬上3的最优花费，算出3的最优花费后我们就可以算出4的，然后就能算出5的…最后我们就能算出爬到n+1的最优花费了，也就是我们的答案

然后我们直接写程序

1
class Solution {
2
public:
3
    int minCostClimbingStairs(vector<int>& cost) {
4
    //传入一个费用数组cost
5
        int n1 = 0,n2=0,curl;
6
    //观察公式可发现，算出n，只需n-1,n-2的费用及其花费，所以只用存两个数
7
    //curl是用来保存n的最优费用
8
        for(int i = 2; i <= std::size(cost); i++){
9
            curl = min(n1 + cost[i-1] , n2 + cost[i-2]);
10
      //算出i的最优费用
11
            n2 = n1;
12
            n1 = curl;
13
        }
14
        return n1;
15
    }
16
};