动态规划之使用最小花费爬楼梯【LeetCode】-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划之使用最小花费爬楼梯【LeetCode】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

LCR 088. 使用最小花费爬楼梯

动态规划之使用最小花费爬楼梯【LeetCode】,算法刷题经验,动态规划,leetcode,算法

解法1

状态表示（这是最重要的）：dp[i]表示以第i级台阶为楼层顶部，到达第i层台阶的最低花费。
状态转移方程（最难的）：dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
初始化：根据题意，我们需要知道到达第1层和第2层台阶的最低花费，第1层和第2层台阶的最低花费为0，并且vector会自动将所有元素初始化为0，所以可以忽略这一步。
填表顺序：当我们求解当前问题时，需要知道所需较小子问题的解，这就需要我们先求解得到较小子问题的解，这就是填表顺序。我们这道解法是从左向右填表。
返回值：n = cost.size(); return dp[n];

代码实现：

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

        return dp[n];
    }
};

解法2

状态表示（这是最重要的）：dp[i]表示从第i级台阶开始，到达楼层顶部的最低花费。
状态转移方程（最难的）：dp[i] = cost[i]+min(dp[i+1], dp[i+2]);
初始化：n = cost.size(); dp[n-1]=cost[n-1], dp[n-2]=cost[n-2];
填表顺序：当我们求解当前问题时，需要知道所需较小子问题的解，这就需要我们先求解得到较小子问题的解，这就是填表顺序。我们这道解法是从右向左填表。
返回值：return min(dp[0], dp[1]);

代码实现：

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

        return min(dp[0], dp[1]);
    }
};