查找Python中给定两个列表中的最终索引的成本的程序

假设我们有两个数字列表nums0和nums1，长度相同，和两个其他值，d作为距离，c为成本。 如果我们从任一nums0或nums1的索引0开始，并希望在任一列表的最终索引结束。 现在，在每轮中，我们可以选择切换到另一个列表，成本为成本。 然后，我们可以以最多d距离向前跳跃，其中着陆索引的c成本是该点的值。 因此，我们必须找到完成任务可能的最小总成本。

因此，如果输入如下nums0 = [2, 3, 10, 10, 6] nums1 = [10, 10, 4, 5, 100] d = 2 c = 3，则输出将为18，因为我们可以从2开始，切换到第二个列表到4，再切换回第一个列表到6。 所以成本为2 + 4 + 6 = 12，切换两次成本为3，因此总成本为18。

为了解决这个问题，我们将遵循以下步骤 −

• switch :=一个以0为nums0的键，1为nums1的键的映射
• 定义函数search()。这将接受idx，nums
• 如果idx >=switch[nums]的大小，则
  • 返回inf
• 如果idx与switch[nums]的大小相同，则
  • 返回switch[nums，-1]
• c :=无限
• 对于i在范围1到dist + 1中，执行以下操作
  • c := c和switch[nums，idx] +搜索（idx + i，nums）的最小值
  • c := c和switch[nums，idx] +成本+搜索（idx + i，nums的反转）的最小值
• 返回c
• 从主方法执行以下操作−
• 返回search（0，0）和search（0，1）的最小值

示例（Python）

让我们看以下实现，以更好地理解−

class Solution:
   def solve(self, nums0, nums1, dist, cost):
      switch = {0: nums0, 1: nums1}
      def search(idx, nums):
         if idx >= len(switch[nums]):
            return float("inf")
         if idx == len(switch[nums]) - 1:
            return switch[nums][-1]
         c = float("inf")
         for i in range(1, dist + 1):
            c = min(c, switch[nums][idx] + search(idx + i, nums))
            c = min(c, switch[nums][idx] + cost + search(idx + i, int(not nums)))
         return c
      return min(search(0, 0), search(0, 1))
ob = Solution()
nums0 = [2, 3, 10, 10, 6]
nums1 = [10, 10, 4, 5, 100]
d = 2
c = 3
print(ob.solve(nums0, nums1, d, c))

输入

[2, 3, 10, 10, 6],[10, 10, 4, 5, 100], 2, 3

输出

18