leetcode746——爬楼梯——动态规划

技术文章 4个月前 完美者
1,687 0

标签:公式   题意   有一个   space   rgb   理论   main   ace   names   

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//原理:动态规划法
//到达每个阶梯都有一个理论上的最小体力minCost,按照minCost[i] = min(minCost[i-2]+cost[i-2],minCost[i-1]+cost[i-1])
//的公式,可以从第一项逐项递推到最后一项的minCost,即题意的最小体力。

//到达第i层阶梯,都只有两种上楼梯的情况:
//1、花费minCost[i-2]到第i-2层,然后花费cost[i-2]跨过两层到第i层;
//2、花费minCost[i-1]到第i-1层,然后花费cost[i-1]跨过一层到第i层。
//举例:i        0    1    2    3    4    (5)
//        cost    1    2    3    4    5    (0)
//        minCost    0    0    1    2    4    (6)
//到i=3的阶梯,有minCost[3] = min(minCost[1]+cost[1],minCost[0]+cost[0])
//                                    2        +    0    ,    0        +    1
//此时,结果是1

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {        

        vector<int> minCost(cost.size()+1);                        //为了计算方便,在最后的minCost加一个空位,视为cost为0的minCost,即结果
        minCost[0] = 0;
        minCost[1] = 0;
        for (int i = 2; i <= cost.size(); i++) {
            minCost[i] = min(minCost[i-2]+cost[i-2],minCost[i-1]+cost[i-1]);
        }
        return minCost[cost.size()];
    }
};

int main()
{
    Solution s;
    vector<int> v = {1,2,3,4,5};
    cout <<s.minCostClimbingStairs(v);
    cout << endl;
}

 

leetcode746——爬楼梯——动态规划

标签:公式   题意   有一个   space   rgb   理论   main   ace   names   

原文地址:https://www.cnblogs.com/Ping697/p/14295513.html

版权声明:完美者 发表于 2021-01-19 12:19:43。
转载请注明:leetcode746——爬楼梯——动态规划 | 完美导航

暂无评论

暂无评论...