一、题目描述

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 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 。

 

提示：

cost 的长度范围是 [2, 1000]。

cost[i] 将会是一个整型数据，范围为 [0, 999] 。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思考

参考的大神的思路：https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/yi-bu-yi-bu-tui-dao-dong-tai-gui-hua-de-duo-chong-/

注意题目描述：每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯

所以示例 1 中只花费一个 15 就可以到阶梯顶，最后一步可以理解为 不用花费。

读完题大家应该知道指定需要动态规划的，贪心是不可能了。

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

使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组 dp[i]就可以了。

dp[i]的定义：第 i 个台阶所花费的最少体力为 dp[i]。（注意这里认为是第一步一定是要花费）

对于 dp 数组的定义，大家一定要清晰！

确定递推公式

可以有两个途径得到 dp[i]，一个是 dp[i-1] 一个是 dp[i-2]。

那么究竟是选 dp[i-1]还是 dp[i-2]呢？

一定是选最小的，所以 dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

注意这里为什么是加 cost[i]，而不是 cost[i-1],cost[i-2]之类的，因为题目中说了：每当你爬上一个阶梯你都要花费对应的体力值

根据 dp 数组的定义，dp 数组初始化其实是比较难的，因为不可能初始化为第 i 台阶所花费的最少体力。

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

所以初始化代码为：

int[] dp(cost.size()); dp[0] = cost[0]; dp[1] = cost[1];

1. 确定遍历顺序

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

三、代码实现

class Solution {    public int minCostClimbingStairs(int[] cost) {        //初始化状态数组        int[] dp = new int[cost.length];        //处理0和1        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];        }        // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }}

时间复杂度为 O(n)

空间复杂度为 O(n)

上面的代码在空间利用上可以再优化一下。

注意到状态转移方程中只用到了前面的两个记录，可以不用一维数组，只用两个变量保存前面的两个记录，并不断更新，就可以递推下去，这样空间复杂度就是 O(1)了。

更进一步，注意到初始值 dp[0] = cost[0]，dp[1] = cost[1]，可以直接复用 cost 数组来代表 dp 数组。

class Solution {    public int minCostClimbingStairs(int[] cost) {        //直接利用数组来代表有状态的数组        for (int i = 2; i < cost.length; i++) {            cost[i] = Math.min(cost[i - 2], cost[i - 1]) + cost[i];        }        return Math.min(cost[cost.length - 2], cost[cost.length - 1]);    }}

时间复杂度为 O(n)

空间复杂度为 O(1)

四、小结

其实这个题和昨天的爬楼梯都是 DP 动态规划题目，解法还有其他几种，但是我觉得这种比较简单适用。