DP- 使用最小花费爬楼梯 DAY19

使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
//从下标为0开始，爬两个阶梯，岂不是只需要10元？不是的，是要跳出数组索引才算到达楼顶！

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：
2 <= cost.length <= 1000
0 <= cost[i] <= 999

我的理解是：从i阶楼梯起跳需要花费力气，跳到数组索引外算到达楼顶，再返回最小花费。

1.确定dp数组以及下标的含义

dp[i]代表到达第i阶楼梯需要的最少花费。

2. 确定递推公式

对于dp[i]，有两种方式，一种是从dp[i-1]爬一层楼梯到达；一种是从dp[i-2]爬两层楼梯到达。所以就有：
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？
一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

3. dp数组初始化

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

dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]、dp[1]推出。

那么dp[0] 应该是多少呢？根据dp数组的定义，到达第0台阶所花费的最小体力为dp[0]，那么有同学可能想，那dp[0] 应该是 cost[0]，例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话，dp[0] 就是cost[0]应该是1。

题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达第 0 个台阶是不花费的，但从第0 个台阶往上跳的话，需要花费 cost[0]。

所以初始化 dp[0] = 0，dp[1] = 0;

4. 确定遍历顺序

因为是模拟台阶，而且dp[i]由dp[i-1]和dp[i-2]推出，所以是从前到后遍历 cost数组就可以了。

5. 举例dp数组

以示例 2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：
在这里插入图片描述

class Solution {
    public int minCostClimbingStairs(int[] cost) {
    // 对应阶梯0,1是不需要花费的; 不是length <= 2，举个例子：[1,100]的楼顶是第三层！花费不是0！
       // if(cost.length <= 1) return 0; 题目中已经说了length >= 2 了
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= cost.length; i++){
            //跳2层
            int a = dp[i - 2] + cost[i - 2];
            //跳1层
            int b = dp[i - 1] + cost[i - 1]; 
            dp[i] = a <= b ? a : b;
        }
        return dp[cost.length];
    }
}

//压缩版
class Solution {
    public int minCostClimbingStairs(int[] cost) {
       // 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。
        int beforeTwoCost = 0, beforeOneCost = 0, currentCost = 0;
        for(int i = 2; i <= cost.length; i++){
            currentCost = Math.min(beforeTwoCost + cost[i-2],beforeOneCost + cost[i-1]);
            beforeTwoCost = beforeOneCost;
            beforeOneCost = currentCost;
        }
        return currentCost;
    }
}

总结

1.对于每个dp[i]都有两种途径到达，那就要计算两种的花费并取最小的一种。
2. 之前是计算求F(n)，得出有多少种方法：是将dp[i-1] + dp[i -2]；现在是min([dp[i-1] + cost(i-1),dp[i-2 + cost(i-2)])；
3. 索引需要超过cost数组的外部【越界】，才算到达楼顶。
4. 为什么要对dp数组进行初始化？因为后面的dp[i]通过递推公式可以倒推回去，整个dp数组的起始值就是初始化所做的工作！

没看懂拓展

也就是说到达第一步时就已经有花费了，再加上起跳的花费，才到达i层？
如果按照第一步是花费的，最后一步不花费

// 方式二：第一步支付费用
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];//
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];//cost[i]就是代表最后一步的花费？
        }
        //最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }
}