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

原题地址：https://leetcode-cn.com/problems/min-cost-climbing-stairs/

原题：

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

注意：

1.cost 的长度将会在 [2, 1000]。
2.每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

思路：
由于这题有些像之前的一道爬楼梯的题，所以自然而然地会想到用动态规划的方法去尝试解题。求到达每一阶的最小成本，然后获取倒数第一和倒数第二的最小值即为解。

把问题缩小，只有两种办法到达第i阶，一种是i-2阶走两步到达，一种是i-1阶走一步到达。如到达第二阶花费cost[2],就有三种方法：

• 1. 从0阶走两个一步到第2阶；
• 2. 从0阶走两步到第2阶；
• 3. 从第1阶走1步到第2阶

虽然从枚举的角度来说，有以上三种，但实际上第一种需要累加两个值，相较于2，3两种都会有无意义的值增加，所以无需考虑。因此只有两种方法到达某一台阶i，因此到达台阶i的花费即为两种方法中代价最小的，可得关系式：cost[i] = min(cost[i-1]+cost[i],cost[i-2]+cost[i]).

代码：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        if (length == 0) return 0;
        if (length == 1) return cost[0];
        if (length == 2) return Math.min(cost[0],cost[1]);
        for (int i = 2; i<length;i++) {
            // 取最小的那个
            cost[i] = Math.min(cost[i-1]+cost[i],cost[i-2]+cost[i]);
        }
        return Math.min(cost[length-1],cost[length-2]);
    }
}

代码提交结果：

image.png