动态规划之使用最小花费爬楼梯【LeetCode】

动态规划之使用最小花费爬楼梯

• LCR 088. 使用最小花费爬楼梯
• • 解法1
  • 解���2

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

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

    解法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& cost) {        int n= cost.size();        vector dp(n+1);        int i = 0;        for(i = 2; i             dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);        }        return dp[n];    }};public:    int minCostClimbingStairs(vector        int n = cost.size();        vector= 0; i--)        {            dp[i] = cost[i]+min(dp[i+1], dp[i+2]);        }        return min(dp[0], dp[1]);    }};

          创作不易，你的点赞和关注都是对我莫大的鼓励，再次感谢您的观看