【动态规划篇】746.使用最小花费爬楼梯

发布于:2025-03-16 ⋅ 阅读:(13) ⋅ 点赞:(0)

在这里插入图片描述
在这里插入图片描述

746.使用最小花费爬楼梯

题目链接: 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


解题思路:
解法一:

  1. 状态表示
    在这里插入图片描述
    dp[0] 表示爬到0位置的最小花费
    dp[1] 表示爬到1位置的最小花费
    dp[2] 表示爬到2位置的最小花费
    .
    .
    dp[i]表示爬到i位置的最小花费
  2. 状态转移方程
    i之前或之后的位置的状态,推导出dp[i]的值
    dp[i]表示到达i位置的最小花费
    要么到达i-1的位置一1步到达i位置,要么到达i-2的位置走两步到达i位置
    🍃根据最近的一步来划分问题
    在这里插入图片描述
    dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2])
  3. 初始化
    保证填表的时候不越界
    dp[0] = dp[1] = 0;
  4. 填表顺序
    从左往右
  5. 返回值
    dp[n]

代码实现:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //1.创建dp表
        int n = cost.size();
        vector<int> dp(n + 1);
        //2.初始化  由于vector的特性不写默认是0;
        for (int i = 2; i <= n; i++)
            //3.dp方程
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

        return dp[n];//最后要爬到楼顶,所以要返回dp[n]
    }
};

时间复杂度:O(n)
空间复杂度:O(n)

解法二:

  1. 状态表示
    dp[i]表示:以i为起点到达楼顶时的最小花费
  2. 状态转移方程
    分为两种情况:
     ➀支付i位置的费用后,从i+1的位置到终点
     ➁支付i位置的费用后,从i+2的位置到终点
    在这里插入图片描述
    dp[i] = min(dp[i + 1] + cost[ i ],dp[i + 2] + cost[ i ])
  3. 初始化
    若从n-1位置出发到达楼顶只需支付n-1位置的费用
    若从n-2位置出发到达楼顶只需支付n-2位置的费用
    在这里插入图片描述
    仅需初始化最后两个位置
    dp[n-1] = cost[n-1],dp[n-2] = cost[n-2]
  4. 填表顺序
    从右往左
  5. 返回值
    min(dp[0],dp[1])

代码实现:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //1.初始化dp表
        //2.初始化
        //3.填表
        //4.返回结果
        int n = cost.size();
        vector<int> dp(n);
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];
        for (int i = n - 3; i >= 0; i--)
        {
            dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
        }
        return min(dp[0], dp[1]);
    }
};

时间复杂度:O(n)
空间复杂度:O(n)


👍 如果对你有帮助,欢迎:

  • 点赞 ⭐️
  • 收藏 📌
  • 关注 🔔