力扣---746. 使用最小花费爬楼梯

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

示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-cost-climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

和之前爬楼梯那个类似，假设有一个九层台阶，爬到最高处需要的花费等于：1、从第八层连续跳两层的花费，即所需的总花费等于从开始到第八层的总花费加第八层的花费。

                                                                                                                           2、从第九层跳一层的花费，即所需的总花费等于从开始到第九层的总花费加第九层的总花费。

依次类推，到第九层的总花费和第七层、第八层有关；第八层的总花费和第六层、第七层有关，每一层的总花费都之和前两层有关。

由于一次可以跳一层或者两层，选择前两层总花费较小的那一层即可。

代码如下：

 1 class Solution {
 2     public int minCostClimbingStairs(int[] cost) {
 3         // 存储每一层的最优花费。
 4         int [] arr = new int[cost.length];
 5         //由于到每一层的总花费和起跳的花费已经确定了，那么直接存储这两样花费之和即可
 6         arr[0] = cost[0];
 7         arr[1] = cost[1];
 8         for (int i = 2; i < cost.length; i ++) {
 9             //每一层的最优花费等于前两层的最低花费加该层起跳所需的花费。
10             arr[i] = Math.min(arr[i - 1], arr[i - 2]) + cost[i];
11         }
12         // 最后两层都可以直接到楼梯顶部，哪个需要的花费少就选择哪个。
13         return Math.min(arr[cost.length - 1], arr[cost.length - 2]);
14     }
15 }

运行结果如下：

由于我们需要前两层所需的花费，所以直接用两个变量存储即可，可以将O(n)的空间消耗降低到O(1)；

代码如下：

 1 class Solution {
 2     public int minCostClimbingStairs(int[] cost) {
 3         //cost = [1,100,1,1,1,100,1,1,100,1]
 4         int a1 = cost[0];
 5         int a2 = cost[1];
 6         int a;
 7         for (int i = 2; i < cost.length; i ++) {
 8             a = Math.min(a2, a1) + cost[i];
 9             a1 = a2;
10             a2 = a;
11         }
12         return Math.min(a1, a2);
13     }
14 }

运行结果如下：

虽然我也不知道为啥常数空间反倒更高了，应该是和数组长度不够长有关。

进一步优化，可以发现cost数组只需要用到第几层的数据，第几层之前的数据都没用，那么可以直接利用cost数组来存储所需花费。

代码如下：

1 class Solution {
2     public int minCostClimbingStairs(int[] cost) {
3         for (int i = 2; i < cost.length; i++) {
4             cost[i] = Math.min(cost[i - 2], cost[i - 1]) + cost[i];
5         }
6         return Math.min(cost[cost.length - 2], cost[cost.length - 1]);
7     }
8 }

运行结果如下：

 可以看出，比上一个所需的空间更少，虽然还是由于数据量不大，比不过O(n)那个。