746. 使用最小花费爬楼梯

2023-12-21 10:41:13


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 - 1length - 2 两层有关, 所以我们不需要设定dp数组, 只需要创建两个int变量即可. 并且设定其初始值.

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

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

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

    最后从 minValue1minValue2 取较小值即为题目的题解.

    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), 常量基本的时间复杂度.

    结果如下所示.

文章来源:https://blog.csdn.net/qq_33591200/article/details/135123547
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。