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

不知道有没有像我一样看这题代码转不过弯来的

主要是很纠结：“其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用”

这句话说明，到i级台阶的时候，还不用付钱，开始爬了才要付钱。

我就转不过弯来，就在代码上转了个弯，改了一下，能看懂代码啦。舒畅了

前言

Y总的代码我转不过弯来，于是我问了问赖哥，学到了，

f[i]: 爬到第i级台阶的最小花费
f[0] = 0 因为可以免费到0级，表示爬到第0级台阶花费，就是0
f[1] = 0,因为可以免费到1级，同上

闫式DP：划分集合，f(i - 2)、f(i - 1)分别表示从i-2级、i-1级再到i级

f[i] = min(f[i - 2] + cost[i - 2], f[i - 1] + cost[i - 1]), 即如果想从第i-2级到i，那就是需要先到i-2，最小花费f[i - 2]，然后花cost[i - 2]，就可以跨两步上i级。

注意：如果cost中有三个元素，表示有台阶：0 1 2，目标是走到顶部，也就是台阶3，所以要多开一个位置，数组开大一个即可。

C++

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> f(n + 1);  // 当n=3，需要计算f0 f1 f2 f3,最后返回f3，所以是4个数（最小DEMO法，不抽象）
        // f3: 爬到第3级台阶的最低花费，如果cost有3个，那就是要爬到3（其实是第4级，第1级是0，第2级是1，第3级是2，第4级是3）
        f[0] = 0;
        f[1] = 0;
        for (int i = 2; i < n + 1; i ++ ) {
            f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        }
        return f[n];
    }
};

Java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] f = new int[cost.length + 1];  // 如果length=3，那数组是0 1 2三个坑，要想返回第四个坑3，得多开一个
        f[0] = 0;
        f[1] = 0;
        for (int i = 2; i < cost.length + 1; i ++ ) {
            f[i] = Math.min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        }

        return f[cost.length];
    }
}