資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告