मान लीजिए हमारे पास nums नाम की संख्याओं की एक सूची है और एक अन्य मान k है। यहां nums[i] पर आइटम इंडेक्स i पर लैंड करने की लागत को दर्शाते हैं। यदि हम इंडेक्स 0 से शुरू करते हैं और nums के अंतिम इंडेक्स पर समाप्त होते हैं। प्रत्येक चरण में हम किसी स्थिति X से k स्टेप दूर तक किसी भी स्थिति पर कूद सकते हैं। हमें अंतिम इंडेक्स तक पहुंचने के लिए लागतों के योग को न्यूनतम करना है, तो न्यूनतम योग क्या होगा?
इसलिए, यदि इनपुट इस तरह है nums = [2, 3, 4, 5, 6] k = 2, तो आउटपुट 12 होगा, क्योंकि हम 2 + 4 + 6 चुनकर 12 की न्यूनतम लागत प्राप्त कर सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- ans := 0
- h := एक खाली हीप
- i के लिए 0 से nums के आकार तक रेंज में, करें
- val := 0
- जब तक h खाली नहीं है, करें
- [val, index] := h[0]
- यदि index >= i - k, तो
- लूप से बाहर आएं
- अन्यथा,
- हीप h से शीर्ष हटाएं
- ans := nums[i] + val
- पेयर (ans, i) को हीप h में डालें
- ans लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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
आउटपुट
12
