0746.使用最小花费爬楼梯
难度：🟢 简单
标签：数组、动态规划
题目描述
给你一个整数数组 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 。
解题思路
核心思想
本题是动态规划的经典应用。问题的核心是，要到达第 i 个台阶（或者说，要从第 i 个台阶往上爬），我们只能从第 i-1 个或第 i-2 个台阶过来。因此，到达第 i 个台阶的最小花费，取决于到达前两个台阶的最小花费。
思路选择
动态规划 (Dynamic Programming) 是解决此问题的标准最优思路。
我们可以定义一个
dp数组，其中dp[i]表示到达第i个台阶所需的最低花费。我们的目标是到达“楼顶”，可以看作是第cost.length个台阶。状态转移方程 的推导如下：要到达第
i阶，我们可以从第i-1阶爬一步上来，也可以从第i-2阶爬两步上来。我们选择花费更小的那条路。从
i-1阶上来的总花费是：到达i-1阶的最低花费 (dp[i-1]) + 从i-1阶向上爬的花费 (cost[i-1])。从
i-2阶上来的总花费是：到达i-2阶的最低花费 (dp[i-2]) + 从i-2阶向上爬的花费 (cost[i-2])。
因此，状态转移方程为：
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
关键步骤
初始化：
dp[0] = 0：到达第 0 阶之前（在地面上）的花费是 0。dp[1] = 0：由于我们可以直接从第 1 阶开始，所以到达第 1 阶之前也不需要花费。
循环迭代：从
i = 2开始循环到cost.length。状态转移：在循环中，根据状态转移方程计算
dp[i]的值。空间优化：观察发现，计算
dp[i]只需要dp[i-1]和dp[i-2]。因此，我们无需创建完整的dp数组，只需用两个变量滚动记录前两个状态即可。返回结果：循环结束后，
dp[cost.length]就是到达楼顶的最低花费。
代码实现 (推荐)
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
// a 代表 dp[i-2], b 代表 dp[i-1]
let prev2 = 0;
let prev1 = 0;
for (let i = 2; i <= cost.length; i++) {
const current = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
// 滚动更新
prev2 = prev1;
prev1 = current;
}
return prev1;
};
原始代码分析 (用户提供)
您提供的代码是此问题的标准动态规划解法，逻辑完全正确，但空间复杂度可以被优化。
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function (cost) {
let dp = [];
// dp[i] 表示到达第 i 阶的最小花费
// dp[0] 和 dp[1] 初始化为 0，因为可以选择从 0 或 1 开始，无需花费
dp[0] = 0;
dp[1] = 0;
// 从第 2 阶开始计算
for (let i = 2; i <= cost.length; i++) {
// 状态转移方程正确
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
// 最终结果是到达楼顶（第 cost.length 阶）的最小花费
return dp[cost.length];
};
优点：此实现清晰地展示了动态规划的状态定义和转移过程，是理解该问题的好起点。
待改进：该解法使用了 O(n) 的额外空间来存储
dp数组。推荐代码中通过使用两个变量进行“滚动”，将空间复杂度优化到了 O(1)。
复杂度分析
时间复杂度：O(n) 其中 n 是数组
cost的长度。我们只需要对数组进行一次完整的遍历。空间复杂度：O(1) 推荐解法只使用了常数个额外变量，空间消耗是恒定的。
相关题目
总结
本题是动态规划中“爬楼梯”问题的变种，核心在于理解状态的定义和转移。dp[i] 定义为“到达第 i 阶的最小花费”是解题的关键。通过状态压缩（滚动数组）可以进一步优化空间复杂度，是动态规划问题中常用的技巧。