一、题目
给你一个整数数组 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
二、题解
直接用动规五部曲开始分析：
- 确定 dp 数组以及下标的含义
本题只需要一个一维数组 dp[i] 就可以了。
dp[i] 的定义：到达第 i 台阶所花费的最少体力为 dp[i] 。
- 确定递推公式
到达第 i 台阶可以直接从第 i-1 台阶往上跳，也可由第 i-2 台阶往上跳。但如何确定最小花费呢？这就需要明确 dp 数组的含义，到达第 i 台阶的最小花费等于到达第 i-1 台阶的最小花费 + 第 i-1 台阶往上跳的花费，或者等于到达第 i-2 台阶的最小花费 + 第 i-2 台阶往上跳的花费，两者再取较小值即可。
由此可推出递推公式：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
- dp 数组如何初始化
由递归公式可看出，只初始化 dp[0] 和 dp[1] 就够了，其他的最终都是由 dp[0] 和 dp[1] 推出。
新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯”。也就是说从到达第 0 个台阶是不花费的，但从第 0 个台阶往上跳的话，需要花费 cost[0]。
所以初始化 dp[0] = 0，dp[1] = 0。
- 确定遍历顺序
dp[i] 由 dp[i-1] 和 dp[i-2] 推出，所以从前到后遍历 cost 数组就可以了。
- 举例推导 dp 数组
拿示例 2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]，来模拟一下 dp 数组的状态变化，如下：
dp = [0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 6]
如果代码写出来有问题，就把 dp 数组打印出来，看看和如上推导的是不是一样的
三、代码
public class T746 {
// 非压缩版本
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= cost.length; i++) {
// dp[i]=Integer.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.length];
}
// 压缩版本
public int minCostClimbingStairs2(int[] cost) {
int dp0 = 0;
int dp1 = 0;
int dpi;
for (int i = 2; i <= cost.length; i++) {
dpi = Math.min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
dp0 = dp1;
dp1 = dpi;
}
return dp1;
}
}