數(shù)組的每個(gè)下標(biāo)作為一個(gè)階梯，第 i 個(gè)階梯對(duì)應(yīng)著一個(gè)非負(fù)數(shù)的體力花費(fèi)值 cost[i]（下標(biāo)從 0 開(kāi)始）。
每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力值，一旦支付了相應(yīng)的體力值，你就可以選擇向上爬一個(gè)階梯或者爬兩個(gè)階梯。
請(qǐng)你找出達(dá)到樓層頂部的最低花費(fèi)。在開(kāi)始時(shí)，你可以選擇從下標(biāo)為 0 或 1 的元素作為初始階梯。

狀態(tài)轉(zhuǎn)移方程
dp[i] = min(dp[i-1], dp[i-2]) + dp[i];
邊界條件
dp[0] = cost[0], dp[1] = cost[1]

這題總感覺(jué)題目描述得不太行，cost數(shù)組中的最后一個(gè)元素并不是最高層，而是最高層的下面的一個(gè)樓層。同時(shí)，題目隱含了最高層所需體力值為0這個(gè)條件。

算是第一次獨(dú)立用動(dòng)態(tài)規(guī)劃方法做出動(dòng)態(tài)規(guī)劃的題吧，第一天就刷到這了，暑假繼續(xù)加油。

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

總結(jié)

以上是生活随笔為你收集整理的LeetCode动态规划 使用最小花费爬楼梯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。