美文网首页动态规划LeetCode蹂躏集
LeetCode 746. Min Cost Climbing

LeetCode 746. Min Cost Climbing

作者: alexsssu | 来源:发表于2018-01-25 11:14 被阅读0次

DP解法:定义一个dp数组,dp[i]为到达第i层的最小花费,dp[i]仅与dp[i-1]和dp[i-2]和相应层的cost值有关,满足:dp[i] = min(dp[i-2] + cost[i-2] , dp[i-1] + cost[i-1]);由于i大于等于2,则将dp[0] = dp[1] = 0。

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

相关文章

网友评论

    本文标题:LeetCode 746. Min Cost Climbing

    本文链接:https://www.haomeiwen.com/subject/gfzmaxtx.html