mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
539 lines
17 KiB
Markdown
Executable File
539 lines
17 KiB
Markdown
Executable File
* [做项目（多个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 的台阶开始爬楼梯。
|
||
|
||
请你计算并返回达到楼梯顶部的最低花费。
|
||
|
||
|
||
|
||
|
||
## 思路
|
||
|
||
（**在力扣修改了题目描述下，我又重新修改了题解**）
|
||
|
||
修改之后的题意就比较明确了，题目中说 “你可以选择从下标为 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数组的状态变化，如下：
|
||
|
||
|
||
|
||
如果大家代码写出来有问题，就把dp数组打印出来，看看和如上推导的是不是一样的。
|
||
|
||
以上分析完毕，整体C++代码如下：
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
int minCostClimbingStairs(vector<int>& cost) {
|
||
vector<int> 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<int>& 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<int>& cost) {
|
||
vector<int> 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<n :dp[i] = min(dp[i-1],dp[i-2])+cost[i]
|
||
i==n:dp[i] = min(dp[i-1],dp[i-2]) (登顶)
|
||
|
||
func minCostClimbingStairs(cost []int) int {
|
||
n := len(cost)
|
||
dp := make([]int, n+1)
|
||
dp[0], dp[1] = cost[0], cost[1]
|
||
for i := 2; i <= n; i++ {
|
||
if i < n {
|
||
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
|
||
} else {
|
||
dp[i] = min(dp[i-1], dp[i-2])
|
||
}
|
||
}
|
||
return dp[n]
|
||
}
|
||
func min(a, b int) int {
|
||
if a < b {
|
||
return a
|
||
}
|
||
return b
|
||
}
|
||
```
|
||
|
||
|
||
### JavaScript
|
||
|
||
```JavaScript
|
||
var minCostClimbingStairs = function(cost) {
|
||
const dp = [0, 0]
|
||
for (let 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]
|
||
};
|
||
```
|
||
|
||
不使用 dp 数组
|
||
|
||
```JavaScript
|
||
var minCostClimbingStairs = function(cost) {
|
||
let dpBefore = 0,
|
||
dpAfter = 0
|
||
for(let i = 2;i <= cost.length;i++){
|
||
let dpi = Math.min(dpBefore + cost[i - 2],dpAfter + cost[i - 1])
|
||
dpBefore = dpAfter
|
||
dpAfter = dpi
|
||
}
|
||
return dpAfter
|
||
};
|
||
```
|
||
|
||
### TypeScript
|
||
|
||
```typescript
|
||
function minCostClimbingStairs(cost: number[]): number {
|
||
const dp = [0, 0]
|
||
for (let 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]
|
||
}
|
||
```
|
||
|
||
不使用 dp 数组
|
||
|
||
```typescript
|
||
function minCostClimbingStairs(cost: number[]): number {
|
||
let dpBefore = 0,
|
||
dpAfter = 0
|
||
for (let i = 2; i <= cost.length; i++) {
|
||
let dpi = Math.min(dpBefore + cost[i - 2], dpAfter + cost[i - 1])
|
||
dpBefore = dpAfter
|
||
dpAfter = dpi
|
||
}
|
||
return dpAfter
|
||
}
|
||
```
|
||
|
||
### Rust
|
||
|
||
```Rust
|
||
impl Solution {
|
||
pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> 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>) -> 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 <math.h>
|
||
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 <math.h>
|
||
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]);
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
|