สมมติว่าเรามีรายการตัวเลขสองรายการ nums0 และ nums1 ที่มีความยาวเท่ากัน และค่าอื่นๆ อีกสองค่า d เป็นระยะทาง และ c เป็นต้นทุน หากเราเริ่มต้นจากดัชนี 0 ที่ nums0 หรือ nums1 และต้องการสิ้นสุดที่ดัชนีสุดท้ายของรายการใดรายการหนึ่ง ตอนนี้ในแต่ละรอบเราสามารถเลือกที่จะสลับไปยังรายการอื่นสำหรับต้นทุน จากนั้นเราสามารถกระโดดไปข้างหน้าได้ไกลสุด 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 และเปลี่ยน 2 ครั้งโดยมีค่าใช้จ่าย 3 รายการ รวมเป็น 18
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เปลี่ยน :=แผนที่พร้อมคีย์ 0 สำหรับ nums0 และคีย์ 1 สำหรับ nums1
- กำหนดฟังก์ชัน search() นี่จะใช้เวลา idx, nums
- ถ้า idx>=ขนาดของสวิตช์[nums] แล้ว
- ผลตอบแทน
- ถ้า idx เท่ากับขนาดของสวิตช์[nums] - 1 แล้ว
- สวิตช์ย้อนกลับ[nums, -1]
- c :=inf
- สำหรับฉันอยู่ในช่วง 1 ถึง dist + 1 ทำ
- c :=ขั้นต่ำของ c และ switch[nums, idx] + search(idx + i, nums)
- c :=ขั้นต่ำของ c และ switch[nums, idx] + cost + search(idx + i, invert of nums)
- คืนค
- จากวิธีหลัก ให้ทำดังนี้ -
- ส่งคืนการค้นหาขั้นต่ำ(0, 0) และการค้นหา(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
