数据结构
网络
关系数据库管理系统(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 次浏览
广告