2021-10-31 leetcode 动态规划 746.使用最小花费爬楼梯 c++

2021-10-31 leetcode 动态规划 746.使用最小花费爬楼梯 c++,第1张

2021-10-31 leetcode 动态规划 746.使用最小花费爬楼梯 c++


对于题目的另外一种表述方式:
每个阶梯都有一定数量糖果,一次只能跨一个或者两个阶梯,走到一个阶梯就要吃光上面的糖果,问怎么走才能吃最少的糖果?开局你选前两个阶梯的其中一个作为开头点,并吃光该阶梯的糖果。
思路
当前吃掉的糖果数 ==当前阶梯上有的糖果数 + min(在前1阶时已吃糖果数, 在前2阶时,已吃糖果数);
利用min函数来选择已吃糖果数更少的阶梯,以达到状态转移。
dp[i]为台阶i上的糖果数
状态转移方程:dp[i] += min(dp[i-1], dp[i-2]);

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int l = cost.size();
        int dp[l+1];
        dp[l] = 0;//注意这个值是cost没有赋予的,也就是顶楼的糖果数(0)
        for(int i = 0; i < l; i++) 
            dp[i] = cost[i];
        for(int i = 2; i <= l; i++)
            dp[i] += min(dp[i-1], dp[i-2]);
        return dp[l];
    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/4948622.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-13
下一篇 2022-11-13

发表评论

登录后才能评论

评论列表(0条)

保存