資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python 最小成本爬樓梯
假設有一座樓梯，其中第 i 級臺階會分配一些非負成本值 cost[i]。當我們支付成本時，我們可以爬上一級或兩級臺階。我們必須找到到達樓層頂部的最低成本，我們也可以從索引為 0 或索引為 1 的臺階開始。
因此，如果輸入類似於 cost = [12,17,20]，則輸出將為 17，因為從步驟 1 開始是最便宜的，因為我們必須支付該成本併到達頂部。
為了解決這個問題，我們將遵循以下步驟：
- dp := 一個與 cost 大小相同的陣列，並填充 0
- dp[0] := cost[0]
- 如果 cost 的大小 >= 2，則
- dp[1] := cost[1]
- 對於 i 從 2 到 cost 的大小 - 1，執行以下操作：
- dp[i] := cost[i] + dp[i-1] 和 dp[i-2] 中的最小值
- 返回 dp[-1] 和 dp[-2] 中的最小值
讓我們看看下面的實現，以便更好地理解：
示例
class Solution: def minCostClimbingStairs(self, cost): dp = [0] * len(cost) dp[0] = cost[0] if len(cost) >= 2: dp[1] = cost[1] for i in range(2, len(cost)): dp[i] = cost[i] + min(dp[i-1], dp[i-2]) return min(dp[-1], dp[-2]) ob = Solution() print(ob.minCostClimbingStairs([12,17,20]))
輸入
[12,17,20]
輸出
17
更新於：2020年7月4日
634 次瀏覽
廣告