数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找到达任意两个给定列表的最终索引的成本
假设我们有两个相同长度的数字列表nums0和nums1，以及其他两个值d（距离）和c（成本）。如果我们从nums0或nums1的索引0开始，并希望到达任一列表的最终索引。现在，在每一轮中，我们可以选择以成本c切换到另一个列表。然后我们可以跳跃最多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]的大小-1相同，则
- 返回switch[nums, -1]
- c := 无穷大 (inf)
- 对于范围1到dist + 1中的每个i，执行：
- c := c和switch[nums, idx] + search(idx + i, nums)的最小值
- c := c和switch[nums, idx] + cost + search(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
更新于：2020年12月12日
102 次查看
广告