【每日一题】使用最小花费爬楼梯
Tag
【动态规划+空间优化】【数组】【2023-12-17】
题目来源
解题思路
方法一:动态规划
思路
假设数组 cost
的长度为 n
,则 n
阶楼梯分别对应下标 0
到 n-1
,楼层顶部对应下标 n
,问题等价于计算到达下标 n
的最小花费。可以通过动态规划解决。
接下来对动态规划四部曲的每一步进行具体分析。
状态
创建长度为 n+1
的数组 dp
,dp[i]
表示到达下标 i
的最小花费。
转移关系
因为每次爬楼梯可以爬一阶也可以爬两阶,所以到达下标 i
对应的楼层可以有以下两种方式:
- 从下标
i-1
处使用cost[i-1]
的花费到达下标i
; - 从下标
i-2
处使用cost[i-1]
的花费到达下标i
。
于是,在 2 <= i <= n
时,有如下的状态转移关系:
d p [ i ] = m i n ( d p [ i ? 1 ] + c o s t [ i ? 1 ] , d p [ i ? 2 ] + c o s t [ i ? 2 ] ) dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) dp[i]=min(dp[i?1]+cost[i?1],dp[i?2]+cost[i?2])
base case
由于可以选择下标 0 或 1 作为初始阶梯,并且花费为 0
,因此有 dp[0]=dp[1]=0
。
最后返回
最后返回 dp[n]
,表示到达顶层的最小花费。
算法
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n+1);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; ++i) {
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
return dp[n];
}
};
复杂度分析
时间复杂度:
O
(
n
)
O(n)
O(n),
n
n
n 是数组 cost
的长度。
空间复杂度: O ( n ) O(n) O(n)。
空间优化
思路
观察方法一中的转移关系,我们知道当 i >= 2
时,dp[i]
只和 dp[i-1]
和 dp[i-2]
有关,因此可以使用滚动数组将空间复杂度优化到 O(1)
。
算法
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
int prev = 0, curr = 0;
for (int i = 2; i <= n; ++i) {
int next = min(curr + cost[i-1], prev + cost[i-2]);
prev = curr;
curr = next;
}
return curr;
}
};
复杂度分析
时间复杂度:
O
(
n
)
O(n)
O(n),
n
n
n 是数组 cost
的长度。
空间复杂度: O ( 1 ) O(1) O(1)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!