TNotes.leetcode

Appearance

0746. 使用最小花费爬楼梯【简单】

0746. 使用最小花费爬楼梯【简单】 ​

1. 📝 题目描述 ​

  • 给你一个整数数组 cost，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
  • 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
  • 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
  • 请你计算并返回达到楼梯顶部的最低花费。

示例 1：

txt
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15，向上爬两个台阶，到达楼梯顶部。
总花费为 15。

示例 2：

txt
输入：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。

提示：

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

2. 🫧 评价 ​

  • s.1 - 使用数组记录了抵达所有台阶的最小开支
  • s.2 - 只需要记录当前台阶的前两个台阶的最小开支，即可算出抵达当前台阶的开支，省去了数组的开销
  • 提交结果：
s.1
s.2

3. 🎯 s.1 - 动态规划 ​

js
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  const n = cost.length
  // dp[i] 表示到达第i个台阶的最小花费
  const dp = new Array(n + 1)

  // 初始状态：可以从第0个或第1个台阶开始，所以花费为0
  dp[0] = 0
  dp[1] = 0

  // 状态转移：到达第i个台阶可以从第i-1或第i-2个台阶而来
  for (let i = 2; i <= n; i++) {
    dp[i] = Math.min(
      dp[i - 1] + cost[i - 1], // 从第i-1个台阶爬上来
      dp[i - 2] + cost[i - 2] // 从第i-2个台阶爬上来
    )
  }

  return dp[n] // 到达楼梯顶部的最小花费
}
  • 时间复杂度：O(n)，其中 n 是数组的长度，需要遍历一次数组
  • 空间复杂度：O(n)，需要额外的 dp 数组存储状态

算法思路：

  • 定义 dp[i] 为到达台阶 i 的最低花费（i 表示站在第 i 级台阶的顶部）
  • 初始化：dp[0] = 0、dp[1] = 0（从 0 或 1 开始无需付费）
  • 转移：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])，i 从 2 遍历到 n
  • 答案：dp[n]，其中 n = cost.length，表示到达楼顶的最低花费

4. 🎯 s.2 - 动态规划（空间优化版） ​

js
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  const n = cost.length
  // 只需要记录前两个状态
  let prev2 = 0 // dp[i-2]
  let prev1 = 0 // dp[i-1]

  for (let i = 2; i <= n; i++) {
    const current = Math.min(
      prev1 + cost[i - 1], // 从第i-1个台阶爬上来
      prev2 + cost[i - 2] // 从第i-2个台阶爬上来
    )
    prev2 = prev1
    prev1 = current
  }

  return prev1
}
  • 时间复杂度：O(n)，其中 n 是数组的长度
  • 空间复杂度：O(1)，只使用了常数个额外变量

算法思路：

  • 使用两个变量压缩 dp 数组，分别表示 dp[i-2] 与 dp[i-1]
  • 初始化：prev2 = 0、prev1 = 0
  • 迭代：对 i 从 2 到 n，计算 current = min(prev1 + cost[i-1], prev2 + cost[i-2])，再更新 prev2 = prev1、prev1 = current
  • 返回 prev1 作为 dp[n]

Discussions