पायथन में सीढ़ियों के शीर्ष पर चढ़ने की न्यूनतम लागत ढूंढने का प्रोग्राम

मान लीजिए हमारे पास stairs नामक संख्याओं की एक सूची है और एक अन्य मान k है। हम वर्तमान में सीढ़ी 0 पर हैं और stairs के अंतिम इंडेक्स पर चढ़ना चाहते हैं। मान stair[i] इंडेक्स पर पहुंचने की लागत इंगित करता है और प्रत्येक राउंड में हम 1, 2, ... k, सीढ़ियों को एक बार में कूद सकते हैं। हमें अंतिम सीढ़ी पर चढ़ने की न्यूनतम लागत ढूंढनी है।

उदाहरण के लिए, यदि इनपुट stairs = [4, 11, 11, 3, 2] k = 3 है, तो आउटपुट 9 होगा, क्योंकि हम सीढ़ियों [4, 3, 2] का उपयोग करते हैं।

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

q := एक डबल एंडेड क्यू और इसमें एक जोड़ी (stairs[0], 0) डालें
i को 1 से stairs के आकार तक रेंज में, करें
- जब तक i - q[0, 1] > k, करें
  - q के बाएं से आइटम हटाएं
- curcost := q[0, 0] + stairs[i]
- जब तक q खाली नहीं है और curcost <= q के अंतिम आइटम का पहला मान, करें
  - q से अंतिम तत्व हटाएं
- (curcost, i) को q के अंत में डालें
q के अंतिम आइटम का पहला मान लौटाएं

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

उदाहरण

from collections import deque class Solution:    def solve(self, stairs, k):       q = deque([(stairs[0], 0)])       for i in range(1, len(stairs)):          while i - q[0][1] > k:             q.popleft()          curcost = q[0][0] + stairs[i]          while q and curcost <= q[-1][0]:             q.pop()          q.append((curcost, i))       return q[-1][0] ob = Solution() stairs = [4, 11, 11, 3, 2] k = 3 print(ob.solve(stairs, k))

इनपुट

[4, 11, 11, 3, 2], 3