厦门网站建设兼职,淘宝价格网站建设,ppt素材大全免费,wordpress 改为中文字体文章目录 Tag题目来源解题思路方法一#xff1a;动态规划空间优化 写在最后 Tag
【动态规划空间优化】【数组】【2023-12-17】 题目来源
746. 使用最小花费爬楼梯 解题思路
方法一#xff1a;动态规划
思路
假设数组 cost 的长度为 n#xff0c;则 n 阶楼梯分别对应下标… 文章目录 Tag题目来源解题思路方法一动态规划空间优化 写在最后 Tag
【动态规划空间优化】【数组】【2023-12-17】 题目来源
746. 使用最小花费爬楼梯 解题思路
方法一动态规划
思路
假设数组 cost 的长度为 n则 n 阶楼梯分别对应下标 0 到 n-1楼层顶部对应下标 n问题等价于计算到达下标 n 的最小花费。可以通过动态规划解决。
接下来对动态规划四部曲的每一步进行具体分析。
状态
创建长度为 n1 的数组 dpdp[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(vectorint cost) {int n cost.size();vectorint dp(n1);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(vectorint 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)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
