思路

注意題目描述：每當你爬上一個階梯你都要花費對應的體力值，一旦支付了相應的體力值，你就可以選擇向上爬一個階梯或者爬兩個階梯

所以示例1中只花費一個15 就可以到階梯頂，最后一步可以理解為 不用花費。

確定dp數組以及下標的含義

使用動態規劃，就要有一個數組來記錄狀態，本題只需要一個一維數組dp[i]就可以了。

dp[i]的定義：到達第i個臺階所花費的最少體力為dp[i]。（注意這里認為是第一步一定是要花費）

確定遞推公式

可以有兩個途徑得到dp[i]，一個是dp[i-1] 一個是dp[i-2]。

那么究竟是選dp[i-1]還是dp[i-2]呢？

一定是選最小的，所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

注意這里為什么是加cost[i]，而不是cost[i-1],cost[i-2]之類的，因為題目中說了：每當你爬上一個階梯你都要花費對應的體力值

可以理解為到達對應階梯都要給過路費

dp數組如何初始化

根據dp數組的定義，dp數組初始化其實是比較難的，因為不可能初始化為第i臺階所花費的最少體力。

那么看一下遞歸公式，dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就夠了，其他的最終都是dp[0]、dp[1]推出。

所以初始化代碼為：

vector dp(cost.size());
dp[0] = cost[0];
dp[1] = cost[1];

確定遍歷順序

最后一步，遞歸公式有了，初始化有了，如何遍歷呢？

本題的遍歷順序其實比較簡單。

因為是模擬臺階，而且dp[i]又由dp[i-1]和dp[i-2]推出，所以是從前到后遍歷cost數組就可以了。

舉例推導dp數組

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，來模擬一下dp數組的狀態變化，如下：

時間復雜度：O(n) 空間復雜度：O(n) class Solution { public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size());dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < cost.size(); i++) {dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];}// 注意最后一步可以理解為不用花費，所以取倒數第一步，第二步的最少值return min(dp[cost.size() - 1], dp[cost.size() - 2]);} };

總結

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

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