Chương trình tìm chi phí nhỏ nhất đến cuối một trong hai danh sách trong Python

Cho hai danh sách nums0, nums1 cùng độ dài, khoảng cách nhảy tối đa d, chi phí chuyển danh sách c. Bắt đầu tại chỉ số 0 của một trong hai danh sách, muốn đến chỉ số cuối của một trong hai. Mỗi bước: có thể chuyển danh sách (tốn c), sau đó nhảy tới đa d bước. Chi phí đáp ứng tại ô là giá trị ô đó. Tìm tổng chi phí nhỏ nhất.

Ví dụ: nums0=[2,3,10,10,6], nums1=[10,10,4,5,100], d=2, c=3 → đường đi: 2 (nums0[0]) → chuyển → 4 (nums1[2]) → chuyển → 6 (nums0[4]). Chi phí: 2+4+6 + 2*3 = 18.

Giải thuật (Đệ quy + Memoization)

• Hàm search(idx, list_id) trả về chi phí nhỏ nhất từ idx trên danh sách list_id đến cuối.
• Cơ sở: nếu idx là chỉ số cuối → trả về giá trị ô đó. Nếu vượt quá → vô cực.
• Thử nhảy 1..d bước: ở lại danh sách hoặc chuyển danh sách (cộng c). Lấy min.
• Memoization để tránh tính lại.

Mã nguồn Python

class Solution:
    def solve(self, nums0, nums1, dist, cost):
        switch = {0: nums0, 1: nums1}
        from functools import lru_cache
        @lru_cache(None)
        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))  # Output: 18

Đầu vào

[2, 3, 10, 10, 6], [10, 10, 4, 5, 100], 2, 3

Đầu ra

18