一:題目

二:上碼

class Solution { public:/**思路:1.分析題意給出的數組的下標代表樓梯的臺階數2.動態規劃五步走1>:確定dp數組以及下標的含義dp[i]:表示到達第i層所需要花費的體力2>:確定dp數組的遞推公式那么如何得到dp[i](花費的體力)呢？dp[i]由dp[i-1]或者dp[i-2]可以得到，但是我們需要在其中選取一個小的dp[i] = min(dp[i-1],dp[i-2]) + cost[i];為甚要加上cost[i],題目中給出了,我們每到一個臺階的話,需要支付cost[i]才能繼續向上爬3>:確定dp數組的初始化cost.size() == 2那么的話,可以直接一步到樓頂(那就不用花費)，也可以從0開始dp[0] = cost[0],然后再來一步到達樓頂 那就直接返回dp[0]和dp[1]中比較小的那個 (如果這個size() == 2) cost.size() > 2dp[0] = cost[0];dp[1] = cost[1];4>:確定dp數組的遍歷順序這個肯定也是需要從前往后遍歷,因為我們需要前面花費的體力5>:舉例驗證cost = [10,15,2,10]dp[3] = min(dp[2],dp[1]) (這里不用加上cost[3],因為最后一步就直接登頂了)dp[2] = min(dp[1],dp[0]) + cost[2]; **/int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int>dp(n+1);dp[0] = cost[0];dp[1] = cost[1];if(n == 2) return min(dp[0],dp[1]);for(int i = 2; i <= n; i++) {if(i == n){//最后一步是直接到達樓頂的，不需要計算樓頂那層的自己的費用dp[i] = min(dp[i-1],dp[i-2]);}else{dp[i] = min(dp[i-1],dp[i-2]) + cost[i];}}return dp[n];} };

總結

以上是生活随笔為你收集整理的leetcode746. 使用最小花费爬楼梯的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。