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 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习
广告