給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。請你計算并返回達到樓梯頂部的最低花費。示例 1：輸入：cost = [10,15,20] 輸出：15 解釋：你將從下標為 1 的臺階開始。 - 支付 15 ，向上爬兩個臺階，到達樓梯頂部。 總花費為 15 。示例 2：輸入：cost = [1,100,1,1,1,100,1,1,100,1] 輸出：6 解釋：你將從下標為 0 的臺階開始。 - 支付 1 ，向上爬兩個臺階，到達下標為 2 的臺階。 - 支付 1 ，向上爬兩個臺階，到達下標為 4 的臺階。 - 支付 1 ，向上爬兩個臺階，到達下標為 6 的臺階。 - 支付 1 ，向上爬一個臺階，到達下標為 7 的臺階。 - 支付 1 ，向上爬兩個臺階，到達下標為 9 的臺階。 - 支付 1 ，向上爬一個臺階，到達樓梯頂部。 總花費為 6 。

步驟一、確定狀態:

確定dp數組以及下標的含義 dp[i]:到達第i個臺階所花費的最少體力為dp[i]

步驟二、推斷狀態方程:

dp[i]=min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]

到達第i階臺階所需要花費的最小體力， 應該是在第i?1階臺階所需要花費的最 小體力+從i?1階跳一步到第i階所需要的體力和在i?2階所需要花費的最小體力 +從i?2階跳兩步到第i階體力的最小值。

步驟三、規定初始條件:

初始條件:

根據動態轉移方程， 當前狀態是依賴于前兩個狀態的，所以要初始化兩個狀態 dp[0], dp[1]， 而這兩個狀態的初始化，應該是依賴于cost數組的。

dp[0] = 0, dp[1]=0

在0階的時候，我是不用爬的，不需要花費體力，而第1階臺階，我也是先不用 爬的，因為題目里面說可以把0或者1作為初始臺階， 直接站上去即可。

步驟四、計算順序:

還是從前往后 先計算第1階:dp[1] 計算第2階:dp[2]
... 計算第最后一階:dp[-1]

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0] * (len(cost) + 1)dp[0] = 0dp[1] = 0for i in range(2, len(cost) + 1):dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])return dp[-1]

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的85. Leetcode 746. 使用最小花费爬楼梯 (动态规划-基础题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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