पायथन में अधिकतम k चरणों के साथ अंतिम सूचकांक तक पहुंचने के लिए न्यूनतम लागत खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है और दूसरा मान k है। यहां अंक [i] पर आइटम इंडेक्स i पर उतरने की लागत का प्रतिनिधित्व करते हैं। यदि हम सूचकांक 0 से शुरू करते हैं और अंकों के अंतिम सूचकांक पर समाप्त होते हैं। प्रत्येक चरण में हम किसी स्थिति X से k कदम दूर किसी भी स्थिति में कूद सकते हैं। हमें अंतिम इंडेक्स तक पहुंचने के लिए लागतों के योग को कम करना होगा, तो न्यूनतम राशि क्या होगी?

इसलिए, यदि इनपुट संख्या =[2, 3, 4, 5, 6] k =2 जैसा है, तो आउटपुट 12 होगा, क्योंकि हम 12 की न्यूनतम लागत प्राप्त करने के लिए 2 + 4 + 6 का चयन कर सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

उत्तर:=0
h :=एक खाली ढेर
मैं के लिए 0 से लेकर अंकों के आकार तक, करें
- वैल:=0
- जबकि h खाली नहीं है, करें
  - [वैल, इंडेक्स] :=h[0]
  - यदि अनुक्रमणिका>=i - k, तो
    - लूप से बाहर आएं
  - अन्यथा,
    - हीप एच से शीर्ष हटाएं
- उत्तर:=अंक[i] + वैल
- हीप एच में जोड़ी (उत्तर, i) डालें
वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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))

इनपुट

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