Giả sử chúng ta có hai danh sách các số nums0 và nums1 có cùng độ dài và hai giá trị khác d là khoảng cách và c là chi phí. Nếu chúng ta bắt đầu từ chỉ mục 0 tại nums0 hoặc nums1 và muốn kết thúc ở chỉ mục cuối cùng của một trong hai danh sách. Bây giờ, trong mỗi vòng, chúng ta có thể chọn chuyển sang danh sách khác để biết chi phí. Sau đó, chúng ta có thể nhảy về phía trước ở cách xa nhất d khoảng cách mà chi phí c của việc hạ cánh tại một chỉ số là giá trị tại điểm đó. Vì vậy, chúng tôi phải tìm tổng chi phí tối thiểu có thể để hoàn thành nhiệm vụ.
Vì vậy, nếu đầu vào là nums0 =[2, 3, 10, 10, 6] nums1 =[10, 10, 4, 5, 100] d =2 c =3, thì đầu ra sẽ là 18, như chúng ta có thể bắt đầu từ 2, sau đó chuyển sang danh sách thứ hai thành 4, một lần nữa chuyển trở lại danh sách đầu tiên thành 6. Vậy chi phí 2 + 4 + 6 =12 và chuyển hai lần với chi phí 3 mỗi lần nên tổng là 18.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- switch:=một bản đồ có phím 0 cho nums0 và phím 1 cho nums1
- Xác định một hàm tìm kiếm (). Điều này sẽ lấy idx, nums
- if idx> =size of switch [nums], then
- thông tin trở lại
- nếu idx giống với kích thước của switch [nums] - 1, thì
- công tắc trả về [nums, -1]
- c:=inf
- đối với tôi trong phạm vi 1 đến dist + 1, thực hiện
- c:=tối thiểu của c và chuyển đổi [nums, idx] + search (idx + i, nums)
- c:=tối thiểu của c và chuyển đổi [nums, idx] + cost + search (idx + i, invert of nums)
- trả về c
- từ phương thức chính, hãy làm như sau -
- trả về tìm kiếm tối thiểu (0, 0) và tìm kiếm (0, 1)
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)) Đầu vào
[2, 3, 10, 10, 6],[10, 10, 4, 5, 100], 2, 3
Đầu ra
18