03、使用最小花费爬楼梯
大约 7 分钟数据结构算法算法基地面试动态规划刷题程序厨校招社招
今天给大家分享一下，使用最小花费爬楼梯这道经典题目，大家完成之前题目的话，这个题目则完全没有压力啦
https://leetcode.cn/problems/min-cost-climbing-stairs/
题目描述
给你一个整数数组 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]
0 1 2 3 4 5 6 7 8 9
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1，向上爬一个台阶，到达楼梯顶部。
总花费为 6。
约束条件:
2 <= cost.length <= 10000 <= cost[i] <= 999
所以我们要见缝插针，选择花费最小的台阶
问题理解
关键概念理解
重要概念：
1. cost[i] 是什么？
cost[i] 是从第 i 个台阶向上爬的费用
注意：是"离开"该台阶的费用，不是"到达"的费用
2. 楼梯顶部在哪？
在数组之外！
如果 cost = [10,15,20]，顶部在索引 3 的位置
即：顶部 = cost.length
3. 可以从哪开始？
从索引 0 或索引 1 开始
这两个位置都可以免费站上去
4. 每次可以爬几步？
支付费用后，可以爬 1 步或 2 步
图解示例
示例 1：cost = [10,15,20]
索引: 0 1 2 顶部
台阶: [10] [15] [20] [目标]
费用: 10 15 20 -
路径分析：
路径1：从索引 0 开始
0 -> 支付10 -> 1 -> 支付15 -> 顶部
总费用：10 + 15 = 25
路径2：从索引 0 开始
0 -> 支付10 -> 2 -> 支付20 -> 顶部
总费用：10 + 20 = 30
路径3：从索引 1 开始
1 -> 支付15 -> 顶部（爬2步）
总费用：15 ✓ 最小
路径4：从索引 1 开始
1 -> 支付15 -> 2 -> 支付20 -> 顶部
总费用：15 + 20 = 35
答案：15
递推关系分析
如何到达第 i 个台阶？
有两种方式：
1. 从第 i-1 个台阶爬 1 步
花费：到达 i-1 的最小花费 + cost[i-1]
2. 从第 i-2 个台阶爬 2 步
花费：到达 i-2 的最小花费 + cost[i-2]
递推公式：
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
其中 dp[i] 表示到达第 i 个台阶的最小花费
解题思路
动态规划⭐
核心思想
使用 DP 数组，自底向上计算到达每个台阶的最小花费。
DP 五部曲
1. 确定 dp 数组及下标含义
dp[i] 表示到达第 i 个台阶的最小花费
2. 确定递推公式
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
3. dp 数组如何初始化
dp[0] = 0 （可以免费站在索引 0）
dp[1] = 0 （可以免费站在索引 1）
4. 确定遍历顺序
从前往后，i 从 2 到 n（n = cost.size()）
5. 举例推导 dp 数组
cost = [10,15,20]
dp[0] = 0
dp[1] = 0
dp[2] = min(dp[1]+cost[1], dp[0]+cost[0]) = min(0+15, 0+10) = 10
dp[3] = min(dp[2]+cost[2], dp[1]+cost[1]) = min(10+20, 0+15) = 15 ✓
详细图解示例
以 cost = [1,100,1,1,1,100,1,1,100,1] 为例：
索引: 0 1 2 3 4 5 6 7 8 9 顶部(10)
cost: [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] -
步骤1: 初始化
dp[0] = 0 （免费站在索引 0）
dp[1] = 0 （免费站在索引 1）
步骤2: 计算 dp[2]
从索引 0 跳 2 步：dp[0] + cost[0] = 0 + 1 = 1
从索引 1 跳 1 步：dp[1] + cost[1] = 0 + 100 = 100
dp[2] = min(1, 100) = 1
步骤3: 计算 dp[3]
从索引 1 跳 2 步：dp[1] + cost[1] = 0 + 100 = 100
从索引 2 跳 1 步：dp[2] + cost[2] = 1 + 1 = 2
dp[3] = min(100, 2) = 2
步骤4: 计算 dp[4]
从索引 2 跳 2 步：dp[2] + cost[2] = 1 + 1 = 2
从索引 3 跳 1 步：dp[3] + cost[3] = 2 + 1 = 3
dp[4] = min(2, 3) = 2
步骤5: 计算 dp[5]
从索引 3 跳 2 步：dp[3] + cost[3] = 2 + 1 = 3
从索引 4 跳 1 步：dp[4] + cost[4] = 2 + 1 = 3
dp[5] = min(3, 3) = 3
步骤6: 计算 dp[6]
从索引 4 跳 2 步：dp[4] + cost[4] = 2 + 1 = 3
从索引 5 跳 1 步：dp[5] + cost[5] = 3 + 100 = 103
dp[6] = min(3, 103) = 3
步骤7: 计算 dp[7]
从索引 5 跳 2 步：dp[5] + cost[5] = 3 + 100 = 103
从索引 6 跳 1 步：dp[6] + cost[6] = 3 + 1 = 4
dp[7] = min(103, 4) = 4
步骤8: 计算 dp[8]
从索引 6 跳 2 步：dp[6] + cost[6] = 3 + 1 = 4
从索引 7 跳 1 步：dp[7] + cost[7] = 4 + 1 = 5
dp[8] = min(4, 5) = 4
步骤9: 计算 dp[9]
从索引 7 跳 2 步：dp[7] + cost[7] = 4 + 1 = 5
从索引 8 跳 1 步：dp[8] + cost[8] = 4 + 100 = 104
dp[9] = min(5, 104) = 5
步骤10: 计算 dp[10]（顶部）
从索引 8 跳 2 步：dp[8] + cost[8] = 4 + 100 = 104
从索引 9 跳 1 步：dp[9] + cost[9] = 5 + 1 = 6
dp[10] = min(104, 6) = 6 ✓
最终：dp = [0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 6]
答案：6
最优路径：0 -> 2 -> 4 -> 6 -> 7 -> 9 -> 顶部
花费：1 + 1 + 1 + 1 + 1 + 1 = 6
代码实现
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
// 创建 dp 数组，大小为 n+1（包含顶部）
vector<int> dp(n + 1);
// 初始化：可以免费站在索引 0 或 1
dp[0] = 0;
dp[1] = 0;
// 状态转移
for (int i = 2; i <= n; i++) {
// 从 i-1 爬 1 步，或从 i-2 爬 2 步
dp[i] = min(dp[i - 1] + cost[i - 1],
dp[i - 2] + cost[i - 2]);
}
// 返回到达顶部的最小花费
return dp[n];
}
};
时间复杂度: O(n)，遍历一次数组
空间复杂度: O(n)，dp 数组
动态规划空间优化⭐⭐
核心思想
当前状态只依赖前两个状态，使用两个变量即可。
代码实现
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
// 只需要两个变量
int prev2 = 0; // dp[i-2]
int prev1 = 0; // dp[i-1]
// 从索引 2 开始计算到顶部
for (int i = 2; i <= n; i++) {
int curr = min(prev1 + cost[i - 1],
prev2 + cost[i - 2]);
// 滚动更新
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
};
更简洁的写法
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
int a = 0, b = 0;
for (int i = 2; i <= n; i++) {
int c = min(a + cost[i - 2], b + cost[i - 1]);
a = b;
b = c;
}
return b;
}
};
时间复杂度: O(n)
空间复杂度: O(1)
