题目
给你一个整数数组 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$
题解
思路1 贪婪 模拟 （自下而上）
- 能走两步，绝不走一部
- 能省点钱就省点钱
class Solution {
public int minCostClimbingStairs(int[] cost) {
// 模拟爬楼梯，取最小值
int index = -1;
int costSum = 0;
while(index < cost.length - 2) {
// 走一步比走两步的代价小，且走两步之后还要走
// 如果走一步，至少还得走一步 需要判断两步代价之和
// 如果走一步，可以不走了
if (cost[index + 1] == 0 || cost[index + 1] < cost[index + 2] && ((index + 3 == cost.length) || (index + 3 < cost.length && cost[index + 1] + cost[index + 3] <= cost[index + 2]))) {
costSum += cost[index + 1];
// System.out.println("cost[index + 1] = "+ cost[index + 1]);
index += 1;
} else { // 代价一样，肯定走两步
costSum += cost[index + 2];
// System.out.println("cost[index + 2] = "+ cost[index + 2]);
index += 2;
}
}
return costSum;
}
}
/**
* bad case [0, 1, 2, 2, 2] 解决方案：看见 0 花费，必须白票
* bad case [1,2,2,2] 这个不行了，策略有冲突，单调递增和非单调的冲突
* 缺乏全局视野
* **/
动态规划 （自上而下推倒，自下而上实现）
定义$dp[i]$ 为到达i位置的最小花费，两种情况：
- 从 $i-1$ 到达 $dp[i] = dp[i-1] + cost[i-1]$
- 从 $i - 2$ 到达 $dp[i] = dp[i-2] + cost[i-2]$
两者取最小,则状态递推公式：
$dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2])$
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
dp[0] = dp[1] = 0;
for (int i = 2;i <= cost.length;i++) {
dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2] + cost[i-2]);
}
return dp[cost.length];
}
}
// 优化空间复杂度
class Solution {
public int minCostClimbingStairs(int[] cost) {
int cur = 0,pre = 0;
for (int i = 2;i <= cost.length;i++) {
int next = Math.min(cur+cost[i-1],pre + cost[i-2]);
pre = cur;
cur = next;
}
return cur;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
