AlgoPressAppearance
0746-使用最小花费爬楼梯
https://leetcode.cn/problems/min-cost-climbing-stairs/
数组的每个下标作为一个阶梯，第 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] 。
思路分析
这题最要紧的是读懂题目本身，题目最后的一步是阶梯顶，注意到阶梯顶的那一步，是不需要花体力值的。
平台 -> [10, 15, 20] -> 阶梯顶，每次走一步或者两步， 10+20 跨一步到阶梯顶， 或者先跨两步到 15 -> 跨两步到阶梯顶
本题是动态规划 dp[i] = min(dp[i-2],dp[i-1]) + cost[i]，即到达本层的消耗是前两阶加本层，或者前一阶加本层，取小
注意： dp[i] 表示到达某层所需要花费的代价，注意最后一步的阶梯顶是不需要花费体力的。
最后要返回的时候，因为到达平台是没有体力值的 return min(dp[i-2],dp[i-1]);
实现代码
csharp
public class Solution {
public int MinCostClimbingStairs(int[] cost) {
int[] minCost = new int[cost.Length];
minCost[0] = cost[0];
minCost[1] = cost[1];
for(int i=2; i<cost.Length; i++){
//走到本层都需要加 cost[i]，可以从前一层+1，或者前两层+2
minCost[i] = Math.Min(minCost[i-2],minCost[i-1]) + cost[i];
}
//注意这里返回的是前一层或者前两层的步数
return Math.Min(minCost[cost.Length - 1],minCost[cost.Length-2]);
}
}
官网解法
注意状态转移方程，是直接计算了当前步骤的最小值
csharp
public class Solution {
public int MinCostClimbingStairs(int[] cost) {
int n = cost.Length;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = Math.Min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}
上述代码可以优化，使用滚动数组，将空间复杂度降低到O(1)
csharp
public class Solution {
public int MinCostClimbingStairs(int[] cost) {
int n = cost.Length;
int prev = 0, curr = 0;
for (int i = 2; i <= n; i++) {
int next = Math.Min(curr + cost[i - 1], prev + cost[i - 2]);
prev = curr;
curr = next;
}
return curr;
}
}
复习:20220514
csharp
public class Solution {
public int MinCostClimbingStairs(int[] cost) {
int n = cost.Length;
int[] dp = new int[n];
dp[0] = cost[0];
dp[1] = cost[1];
for(int i=2;i<n;i++){
dp[i] = Math.Min(dp[i-1],dp[i-2]) + cost[i];
}
//返回倒数两个的最小的值
return Math.Min(dp[n-1],dp[n-2]);
}
}