Chương trình tìm chi phí tối thiểu để đạt được chỉ số cuối cùng với nhiều nhất k bước trong python

Giả sử chúng ta có một danh sách các số num và một giá trị khác k. Ở đây, các mục ở nums [i] đại diện cho chi phí để đạt được chỉ số i. Nếu chúng ta bắt đầu từ chỉ mục 0 và kết thúc ở chỉ mục cuối cùng của nums. Trong mỗi bước, chúng ta có thể nhảy từ vị trí X nào đó đến vị trí bất kỳ cách xa k bước. Chúng tôi phải giảm thiểu tổng chi phí để đạt được chỉ số cuối cùng, vậy tổng tối thiểu sẽ là bao nhiêu?

Vì vậy, nếu đầu vào là nums =[2, 3, 4, 5, 6] k =2, thì đầu ra sẽ là 12, vì chúng ta có thể chọn 2 + 4 + 6 để có chi phí tối thiểu là 12.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0
• h:=một đống trống
• đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện
  • val:=0
  • trong khi h không trống, hãy thực hiện
    • [val, index]:=h [0]
    • nếu chỉ mục> =i - k, thì
      • ra khỏi vòng lặp
    • nếu không,
      • xóa phần trên khỏi heap h
  • ans:=nums [i] + val
  • chèn cặp (ans, i) vào heap h
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

from heapq import heappush, heappop
class Solution:
   def solve(self, nums, k):
      ans = 0
      h = []
      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