โปรแกรมหาต้นทุนขั้นต่ำเพื่อถึงดัชนีสุดท้ายของสองรายการใน Python

สมมติว่าเรามีสองรายการ nums0 และ nums1 ความยาวเท่ากัน และค่า d (ระยะกระโดดสูงสุด) และ c (ค่าใช้จ่ายในการสลับรายการ) เริ่มจากดัชนี 0 ของรายการใดรายการหนึ่ง ต้องการไปถึงดัชนีสุดท้ายของรายการใดรายการหนึ่ง ในแต่ละรอบ สามารถเลือกสลับรายการ (จ่ายค่า c) แล้วกระโดดไปข้างหน้าสูงสุด d ตำแหน่ง ค่าใช้จ่ายในการลงจอดคือค่าที่ตำแหน่งนั้น หาต้นทุนรวมขั้นต่ำ

เช่น 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 = 6 รวม 18

ขั้นตอนการแก้ปัญหา (Recursive DFS + Memoization)

switch := {0: nums0, 1: nums1}
ฟังก์ชัน search(idx, nums):
- ถ้า idx >= len(switch[nums]) คืน inf
- ถ้า idx == len(switch[nums]) - 1 คืน switch[nums][-1]
- c := inf
- วน i = 1..dist:
  - c = min(c, switch[nums][idx] + search(idx+i, nums)) (ไม่สลับ)
  - c = min(c, switch[nums][idx] + cost + search(idx+i, 1-nums)) (สลับ)
- คืน c
คืน min(search(0,0), search(0,1))

ตัวอย่างโค้ด

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