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

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

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

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

q :=एक डबल एंडेड कतार और इसमें एक जोड़ी (सीढ़ियाँ [0], 0) डालें
1 से लेकर सीढ़ियों के आकार तक के लिए, करें
- जबकि मैं - q[0, 1]> k, do
  - q के बाईं ओर से आइटम हटाएं
- कर्कॉस्ट :=q[0, 0] + सीढ़ियाँ[i]
- जबकि q खाली नहीं है और और curcost <=q के अंतिम आइटम का पहला मान, करें
  - q से अंतिम तत्व हटाएं
- q के अंत में (curcost, i) डालें
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