* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html) * [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html) * [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html) # 746. 使用最小花费爬楼梯 [力扣题目链接](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] 。 ## 算法公开课 **[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：：[动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯](https://www.bilibili.com/video/BV16G411c7yZ/)，相信结合视频再看本篇题解，更有助于大家对本题的理解**。 ----------- 本题之前的题目描述是很模糊的，看不出来，第一步需要花费体力值，最后一步不用花费，还是说 第一步不花费体力值，最后一步花费。 后来力扣改了题目描述，**新题目描述**： 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 ![](https://file1.kamacoder.com/i/algo/20221031170131.png) ## 思路 （**在力扣修改了题目描述下，我又重新修改了题解**） 修改之后的题意就比较明确了，题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的， 从 下标 0 下标1 开始跳就要花费体力了。 1. 确定dp数组以及下标的含义 使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。 **dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]**。 **对于dp数组的定义，大家一定要清晰！** 2. 确定递推公式 **可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]**。 dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。 dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。 那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？ 一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); 3. dp数组如何初始化 看一下递归公式，dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。 那么 dp[0] 应该是多少呢？ 根据dp数组的定义，到达第0台阶所花费的最小体力为dp[0]，那么有同学可能想，那dp[0] 应该是 cost[0]，例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话，dp[0] 就是 cost[0] 应该是1。 这里就要说明本题力扣为什么改题意，而且修改题意之后 就清晰很多的原因了。 新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。 所以初始化 dp[0] = 0，dp[1] = 0; 4. 确定遍历顺序 最后一步，递归公式有了，初始化有了，如何遍历呢？ 本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。 因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。 > **但是稍稍有点难度的动态规划，其遍历顺序并不容易确定下来**。 > 例如：01背包，都知道两个for循环，一个for遍历物品嵌套一个for遍历背包容量，那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢？ 以及在使用一维dp数组的时候遍历背包容量为什么要倒序呢？ **这些都与遍历顺序息息相关。当然背包问题后续「代码随想录」都会重点讲解的！** 5. 举例推导dp数组 拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下： ![](https://file1.kamacoder.com/i/algo/20221026175104.png) 如果大家代码写出来有问题，就把dp数组打印出来，看看和如上推导的是不是一样的。 以上分析完毕，整体C++代码如下： ```CPP class Solution { public: int minCostClimbingStairs(vector& cost) { vector dp(cost.size() + 1); dp[0] = 0; // 默认第一步都是不花费体力的 dp[1] = 0; for (int i = 2; i <= cost.size(); i++) { dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[cost.size()]; } }; ``` * 时间复杂度：O(n) * 空间复杂度：O(n) 还可以优化空间复杂度，因为dp[i]就是由前两位推出来的，那么也不用dp数组了，C++代码如下： ```CPP // 版本二 class Solution { public: int minCostClimbingStairs(vector& cost) { int dp0 = 0; int dp1 = 0; for (int i = 2; i <= cost.size(); i++) { int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]); dp0 = dp1; // 记录一下前两位 dp1 = dpi; } return dp1; } }; ``` * 时间复杂度：O(n) * 空间复杂度：O(1) 当然如果在面试中，能写出版本一就行，除非面试官额外要求 空间复杂度，那么再去思考版本二，因为版本二还是有点绕。版本一才是正常思路。 ## 拓展 旧力扣描述，如果按照 第一步是花费的，最后一步不花费，那么代码是这么写的，提交也可以通过 ```CPP // 版本一 class Solution { public: int minCostClimbingStairs(vector& cost) { vector dp(cost.size()); dp[0] = cost[0]; // 第一步有花费 dp[1] = cost[1]; for (int i = 2; i < cost.size(); i++) { dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]; } // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值 return min(dp[cost.size() - 1], dp[cost.size() - 2]); } }; ``` 当然如果对 动态规划 理解不够深入的话，拓展内容就别看了，容易越看越懵。 ## 总结 大家可以发现这道题目相对于 昨天的[动态规划：爬楼梯](https://programmercarl.com/0070.爬楼梯.html)又难了一点，但整体思路是一样的。 从[动态规划：斐波那契数](https://programmercarl.com/0509.斐波那契数.html)到 [动态规划：爬楼梯](https://programmercarl.com/0070.爬楼梯.html)再到今天这道题目，录友们感受到循序渐进的梯度了嘛。 每个系列开始的时候，都有录友和我反馈说题目太简单了，赶紧上难度，但也有录友和我说有点难了，快跟不上了。 其实我选的题目都是有目的性的，就算是简单题，也是为了练习方法论，然后难度都是梯度上来的，一环扣一环。 但我也可以随便选来一道难题讲呗，这其实是最省事的，不用管什么题目顺序，看心情找一道就讲。 难的是把题目按梯度排好，循序渐进，再按照统一方法论把这些都串起来，所以大家不要催我哈，按照我的节奏一步一步来就行了。 ## 其他语言版本 以下版本其他语言版本，大多是按照旧力扣题解来写的，欢迎大家在[Github](https://github.com/youngyangyang04/leetcode-master)上[提交pr](https://mp.weixin.qq.com/s/tqCxrMEU-ajQumL1i8im9A)，修正一波。 ### Java ```Java // 方式一：第一步不支付费用 class Solution { public int minCostClimbingStairs(int[] cost) { int len = cost.length; int[] dp = new int[len + 1]; // 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0 dp[0] = 0; dp[1] = 0; // 计算到达每一层台阶的最小费用 for (int i = 2; i <= len; i++) { dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[len]; } } ``` ```Java // 方式二：第一步支付费用 class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length]; 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]); } } ``` ```Java // 状态压缩，使用三个变量来代替数组 class Solution { public int minCostClimbingStairs(int[] cost) { // 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。 int beforeTwoCost = 0, beforeOneCost = 0, currentCost = 0; // 前两个台阶不需要费用就能上到，因此从下标2开始；因为最后一个台阶需要跨越，所以需要遍历到cost.length for (int i = 2; i <= cost.length; i ++) { // 此处遍历的是cost[i - 1]，不会越界 currentCost = Math.min(beforeOneCost + cost[i - 1], beforeTwoCost + cost[i - 2]); beforeTwoCost = beforeOneCost; beforeOneCost = currentCost; } return currentCost; } } ``` ### Python 动态规划（版本一） ```python class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp = [0] * (len(cost) + 1) dp[0] = 0 # 初始值，表示从起点开始不需要花费体力 dp[1] = 0 # 初始值，表示经过第一步不需要花费体力 for i in range(2, len(cost) + 1): # 在第i步，可以选择从前一步（i-1）花费体力到达当前步，或者从前两步（i-2）花费体力到达当前步 # 选择其中花费体力较小的路径，加上当前步的花费，更新dp数组 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) return dp[len(cost)] # 返回到达楼顶的最小花费 ``` 动态规划（版本二） ```python class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp0 = 0 # 初始值，表示从起点开始不需要花费体力 dp1 = 0 # 初始值，表示经过第一步不需要花费体力 for i in range(2, len(cost) + 1): # 在第i步，可以选择从前一步（i-1）花费体力到达当前步，或者从前两步（i-2）花费体力到达当前步 # 选择其中花费体力较小的路径，加上当前步的花费，得到当前步的最小花费 dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]) dp0 = dp1 # 更新dp0为前一步的值，即上一次循环中的dp1 dp1 = dpi # 更新dp1为当前步的最小花费 return dp1 # 返回到达楼顶的最小花费 ``` 动态规划（版本三） ```python class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp = [0] * len(cost) dp[0] = cost[0] # 第一步有花费 dp[1] = cost[1] for i in range(2, len(cost)): dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] # 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值 return min(dp[-1], dp[-2]) ``` 动态规划（版本四） ```python class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) prev_1 = cost[0] # 前一步的最小花费 prev_2 = cost[1] # 前两步的最小花费 for i in range(2, n): current = min(prev_1, prev_2) + cost[i] # 当前位置的最小花费 prev_1, prev_2 = prev_2, current # 更新前一步和前两步的最小花费 return min(prev_1, prev_2) # 最后一步可以理解为不用花费，取倒数第一步和第二步的最少值 ``` ### Go ```Go func minCostClimbingStairs(cost []int) int { f := make([]int, len(cost) + 1) f[0], f[1] = 0, 0 for i := 2; i <= len(cost); i++ { f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]) } return f[len(cost)] } func min(a, b int) int { if a < b { return a } return b } ``` ``` GO 第二种思路: dp[i]表示从i层起跳所需要支付的最小费用 递推公式: i) -> i32 { let mut dp = vec![0; cost.len() + 1]; for i in 2..=cost.len() { dp[i] = (dp[i - 1] + cost[i - 1]).min(dp[i - 2] + cost[i - 2]); } dp[cost.len()] } } ``` 不使用 dp 数组 ```rust impl Solution { pub fn min_cost_climbing_stairs(cost: Vec) -> i32 { let (mut dp_before, mut dp_after) = (0, 0); for i in 2..=cost.len() { let dpi = (dp_before + cost[i - 2]).min(dp_after + cost[i - 1]); dp_before = dp_after; dp_after = dpi; } dp_after } } ``` ### C ```c #include int minCostClimbingStairs(int *cost, int costSize) { int dp[costSize + 1]; dp[0] = dp[1] = 0; for (int i = 2; i <= costSize; i++) { dp[i] = fmin(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]); } return dp[costSize]; } ``` 不使用 dp 数组 ```c #include int minCostClimbingStairs(int *cost, int costSize) { int dpBefore = 0, dpAfter = 0; for (int i = 2; i <= costSize; i++) { int dpi = fmin(dpBefore + cost[i - 2], dpAfter + cost[i - 1]); dpBefore = dpAfter; dpAfter = dpi; } return dpAfter; } ``` ### Scala ```scala object Solution { def minCostClimbingStairs(cost: Array[Int]): Int = { var dp = new Array[Int](cost.length) dp(0) = cost(0) dp(1) = cost(1) for (i <- 2 until cost.length) { dp(i) = math.min(dp(i - 1), dp(i - 2)) + cost(i) } math.min(dp(cost.length - 1), dp(cost.length - 2)) } } ``` 第二种思路: dp[i] 表示爬到第i-1层所需的最小花费，状态转移方程为: dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]) ```scala object Solution { def minCostClimbingStairs(cost: Array[Int]): Int = { var dp = new Array[Int](cost.length + 1) for (i <- 2 until cost.length + 1) { dp(i) = math.min(dp(i - 1) + cost(i - 1), dp(i - 2) + cost(i - 2)) } dp(cost.length) } } ``` ### C# ```csharp public class Solution { public int MinCostClimbingStairs(int[] cost) { int[] dp=new int[2] { cost[0], cost[1] }; for (int i = 2; i < cost.Length; i++) { int temp = Math.Min(dp[0], dp[1])+cost[i]; dp[0]=dp[1]; dp[1]=temp; } return Math.Min(dp[0],dp[1]); } } ```