Chương trình tìm chi phí tối thiểu đến cuối mảng với bước nhảy tối đa k trong Python

Cho danh sách nums và giá trị k. nums[i] = chi phí đáp xuống index i. Bắt đầu index 0, kết thúc index cuối. Mỗi bước nhảy từ X đến vị trí cách tối đa k bước. Tối thiểu hóa tổng chi phí đến cuối.

Ví dụ: nums=[2,3,4,5,6], k=2 → output 12 (chọn 2+4+6).

Thuật toán DP + Min Heap (Sliding Window Minimum):

• dp[i] = chi phí tối thiểu đến index i
• dp[i] = nums[i] + min(dp[j]) với j ∈ [i-k, i-1]
• Dùng min-heap lưu (dp_value, index) để lấy min trong cửa sổ k
• Khi duyệt i: pop heap cho đến khi index >= i-k (trong cửa sổ)
• ans = nums[i] + heap[0].value, push (ans, i)

Triển khai

from heapq import heappush, heappop

class Solution:
    def solve(self, nums, k):
        ans = 0
        h = []  # min-heap của (dp_value, index)
        for i in range(len(nums)):
            val = 0
            while h:
                val, index = h[0]
                if index >= i - k:
                    break
                else:
                    heappop(h)
            ans = nums[i] + val
            heappush(h, (ans, i))
        return ans

ob = Solution()
nums = [2, 3, 4, 5, 6]
k = 2
print(ob.solve(nums, k))

Đầu vào

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

Đầu ra

12

Giải thích: Heap lưu các (dp[j], j) trong cửa sổ trượt size k. val = min dp trong cửa sổ. Phức tạp O(n log k). Base case: i=0, heap rỗng → val=0 → ans=nums[0] (chi phí bắt đầu). Đúng vì dp[0] = nums[0].

Lưu ý: Code giả định chi phí index 0 luôn được tính (bắt đầu tại 0). Nếu không tính chi phí index 0, khởi tạo ans=0 và push (0,0) trước vòng lặp.