746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

难度: 简单

来源: 每日一题 2023.12.17

---

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

class Solution {
    public int minCostClimbingStairs(int[] cost) {

    }
}

分析与题解

---

• 动态规划

  爬楼梯是典型的动态规划问题, 这个题目要求上楼梯的最小花费, 那么能到当前第 i 层的楼梯只有两种方式.

  • 第一种: 通过第 i - 1 层爬 1 步.

  • 第二种: 通过第 i - 2 层爬 2 步.

  对此, 当前第 i 层的楼梯的最小花费如下所示, 这也是当前题的状态转移方程.

  当前i层楼梯的最小花费 = ((当前i - 1层楼梯的最小花费 + 当前i层楼梯的花费), (当前i - 2层楼梯的最小花费 + 当前i层楼梯的花费)).较小值
  

  那么, 我们看一下整体的题解过程, 由于最终上楼花费只与 length - 1 和 length - 2 两层有关, 所以我们不需要设定dp数组, 只需要创建两个int变量即可. 并且设定其初始值.

  int minValue1 = cost[0]; // i - 2 步的最小值数据
  int minValue2 = cost[1]; // i - 1 步的最小值数据
  

  然后就是遍历数组, 不断设定更新 minValue1 和 minValue2 的值即可.

  for (int i = 2; i < cost.length; i++) {
      int minValue = Math.min(cost[i] + minValue1, cost[i] + minValue2);
      minValue1 = minValue2;
      minValue2 = minValue;
  }
  

  最后从 minValue1 和 minValue2 取较小值即为题目的题解.

  return Math.min(minValue1, minValue2);
  

  那么接下来, 我们就看一下整体的题解过程.

  class Solution {
      public int minCostClimbingStairs(int[] cost) {
          // 动态规划
          // 一次只能一步或者两步
          int minValue1 = cost[0]; // i - 2 步的最小值数据
          int minValue2 = cost[1]; // i - 1 步的最小值数据
          for (int i = 2; i < cost.length; i++) {
              int minValue = Math.min(cost[i] + minValue1, cost[i] + minValue2);
              minValue1 = minValue2;
              minValue2 = minValue;
          }
          return Math.min(minValue1, minValue2);
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 与数组长度相关的时间复杂度.
  • 空间复杂度: O(1), 常量基本的时间复杂度.

  结果如下所示.