LeetCode_113_MinCostClimbingStairs

1. question: 使用最小花费爬楼梯（简单）

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-cost-climbing-stairs

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

2. answers

这道题和爬楼梯是类似的，只不过不是找出所有方法，而是找出最小的开销。这道题的题目描述的不是很清楚，给定的数组是当前阶梯爬向下一级阶梯（可以迈一步，也可迈两步）的开销。这也就意味着阶梯长度就是数组的长度加一。

和爬楼梯类似，可以逆推。顶点可由n-2阶梯迈两步到达，也可由n-1阶梯迈一步到达。只需要找到到达n-2阶梯的最优解，以及n-1的最优解，二者对比即可。

继续正向推导，如果只有两个元素，只需取最小值即可。如果有三个元素呢？显然需要比较到达第三个元素的最优解和到达第二个元素的最优解。因为达到第二个元素，可以直接从第二个元素开始，显然最优解就是其自身。到达第三个元素，可由第一个元素到达，也可由第二个元素到达。这就需要比较二者的大小了。

也就是说，我们需要时刻保证前两个元素的最优解，这样，才能取得本元素的最优解。即每个元素的最优解都可由前两个元素求的。代码如下所示：

public class Solution_0113 {

    public int minCostClimbingStairs(int[] cost) {

        if(cost.length <= 2) return Math.min(cost[0], cost[1]);

        // 这里的值，表示达到本节点，并且开始向下迈了的开销。
        int pre = cost[0];
        int post = cost[1];

        int temp = 0;

        // 计算到达本节点的最优解。
        for (int i = 2; i < cost.length; i++) {

            // post就是倒数第二个元素，i就是倒数第一个元素。
            // 到达本元素，有两个选择，pre 迈两步，或者post 迈一步
            // 取最优解，
            temp = Math.min(pre + cost[i], post + cost[i]);

            // 注意，保留前面的节点，以及当前节点。
            pre = post;
            post = temp;
        }

        // 最后，此时temp是最后一个元素的最优解
        // post是倒数第二个元素的最优解（注意，由于更新了，所以pre才是倒数第二个元素）

        return Math.min(pre, temp);
    }

    public static void main(String[] args) {
        System.out.println();

//        int[] cost = {10,15,20};
//        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        int[] cost = {1, 100};

        Solution_0113 s = new Solution_0113();

        System.out.println(s.minCostClimbingStairs(cost));
    }
}

其实temp和post可以合二为一。

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。