动态规划篇746.使用最小花费爬楼梯
【动态规划篇】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
解题思路：
解法一：
状态表示
dp[0]表示爬到0位置的最小花费dp[1]表示爬到1位置的最小花费dp[2]表示爬到2位置的最小花费.
.
dp[i]表示爬到i位置的最小花费状态转移方程
用
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])
初始化
保证填表的时候不越界
dp[0] = dp[1] = 0;填表顺序
从左往右
返回值
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)
解法二：
状态表示
dp[i]表示：以i为起点到达楼顶时的最小花费状态转移方程
分为两种情况：
➀支付
i位置的费用后，从i+1的位置到终点➁支付
i位置的费用后，从i+2的位置到终点dp[i] = min(dp[i + 1] + cost[ i ],dp[i + 2] + cost[ i ])
初始化
若从
n-1位置出发到达楼顶只需支付n-1位置的费用若从
n-2位置出发到达楼顶只需支付n-2位置的费用仅需初始化最后两个位置
dp[n-1] = cost[n-1],dp[n-2] = cost[n-2]填表顺序
从右往左
返回值
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)
👍 如果对你有帮助，欢迎：
- 点赞 ⭐️
- 收藏 📌
- 关注 🔔