資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢使樹高互不相同的最小成本
假設我們有一個名為`heights`的數字列表，表示植物的高度，還有一個名為`costs`的列表，表示將植物高度增加一所需的成本。我們必須找到使`heights`列表中每個高度與其相鄰高度不同的最小成本。
因此，如果輸入類似於`heights = [3, 2, 2]`，`costs = [2, 5, 3]`，則輸出為3，因為我們可以將最後一個高度增加1，這需要3的成本。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式`dp()`。這將接收`idx`和`l_height`。
如果`idx`等於`heights`的大小減1，則
如果`heights[idx]`與`l_height`不同，則返回0；否則返回`costs[idx]`。
`ret := inf` (無窮大)
對於範圍0到2內的i，執行：
如果`heights[idx] + i`與`l_height`不同，則
`ret := min(ret, dp(idx + 1, heights[idx] + i) + costs[idx] * i)`
返回`ret`
在主方法中返回`dp(0, null)`
示例
讓我們看下面的實現來更好地理解：
class Solution:
def solve(self, heights, costs):
def dp(idx, l_height):
if idx == len(heights) - 1:
return 0 if heights[idx] != l_height else costs[idx]
ret = float("inf")
for i in range(3):
if heights[idx] + i != l_height:
ret = min(ret, dp(idx + 1, heights[idx] + i) + costs[idx] * i)
return ret
return dp(0, None)
ob = Solution()
heights = [3, 2, 2]
costs = [2, 5, 3]
print(ob.solve(heights, costs))輸入
[3, 2, 2], [2, 5, 3]
輸出
3
更新於：2020-12-23
177 次瀏覽
廣告