友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

746. 使用最小花费爬楼梯

给你一个整数数组 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 。

提示:

  • 2 <= cost.length <= 1000

  • 0 <= cost[i] <= 999

思路分析

0746 01
  • 一刷

  • 二刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-11 20:23:46
 */
public int minCostClimbingStairs(int[] cost) {
  // dp[i] 表示到底第 i 阶时,所需最少费用
  int[] dp = new int[cost.length + 1];
  // 0 和 1 可以直接站上,所以不需要付费
  dp[0] = 0;
  dp[1] = 0;
  for (int i = 2; i < dp.length; i++) {
    // 第 i 阶,有两种走法
    // 1. 从第 i-1 阶走一步上去,花费: dp[i-1] 走到 i-1 的费用 + cost[i-1](向上的费用)
    // 2. 从第 i-2 阶走两步上去,花肥: dp[i-2] 走到 i-2 的费用 + cost[i-2](向上的费用)
    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  }
  return dp[dp.length - 1];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-16 19:56:08
 */
public int minCostClimbingStairs(int[] cost) {
  int a = 0, b = 0, result = 0;
  for (int i = 2; i <= cost.length; i++) {
    // 第 i 阶,有两种走法
    // 1. 从第 i-1 阶走一步上去,花费: dp[i-1] 走到 i-1 的费用 + cost[i-1](向上的费用)
    // 2. 从第 i-2 阶走两步上去,花肥: dp[i-2] 走到 i-2 的费用 + cost[i-2](向上的费用)
    result = Math.min(a + cost[i - 2], b + cost[i - 1]);
    a = b;
    b = result;
  }
  return result;
}