LeetCode 746. 使用最小花费爬楼梯

技术文章 10个月前 完美者
1,762 0

标签:++   pre   楼梯   stc   滚动   tco   for   左右   ret   

动规问题,如果直接使用滚动数组不开空间会效率更高,所有效率可以提升百分之40左右;

 

状态转移方程:

dp[i]=min(dp[i-1],dp[i-2])+cost[i];

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
       	for (int i = 2; i < cost.size(); i++) {
		    cost[i] = cost[i] + min(cost[i - 1], cost[i - 2]);
        }
        return min(cost[cost.size() - 1], cost[cost.size() - 2]);
    }
};

 

LeetCode 746. 使用最小花费爬楼梯

标签:++   pre   楼梯   stc   滚动   tco   for   左右   ret   

原文地址:https://www.cnblogs.com/songlinxuan/p/14166339.html

版权声明:完美者 发表于 2020-12-25 12:32:04。
转载请注明:LeetCode 746. 使用最小花费爬楼梯 | 完美导航

暂无评论

暂无评论...