पायथन में न्यूनतम लागत चढ़ाई सीढ़ियाँ

मान लीजिए कि एक सीढ़ी है, यहां i-वें चरण में कुछ गैर-ऋणात्मक लागत मूल्य लागत [i] निर्दिष्ट की जाएगी। जब हम लागत का भुगतान करते हैं, तो हम या तो एक या दो कदम चढ़ सकते हैं। हमें मंजिल के शीर्ष तक पहुंचने के लिए न्यूनतम लागत का पता लगाना होगा, और हम या तो सूचकांक 0 के साथ कदम से शुरू कर सकते हैं, या सूचकांक 1 के साथ कदम उठा सकते हैं।

इसलिए, यदि इनपुट लागत =[12,17,20] की तरह है, तो आउटपुट 17 होगा, चरण 1 से शुरू करने के लिए सबसे सस्ती स्थिति क्योंकि हमें उस लागत का भुगतान करना होगा और शीर्ष पर जाना होगा।

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

dp :=लागत के समान आकार की एक सरणी, और 0 से भरें
dp[0] :=लागत[0]
यदि लागत का आकार>=2, तो
- dp[1] :=लागत[1]
मैं के लिए 2 से लेकर लागत के आकार -1 तक के लिए
- dp[i] :=लागत[i] + न्यूनतम dp[i-1], dp[i-2]
न्यूनतम डीपी[-1], डीपी[-2]

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

उदाहरण

class Solution:
   def minCostClimbingStairs(self, cost):
      dp = [0] * len(cost)
      dp[0] = cost[0]
      if len(cost) >= 2:
         dp[1] = cost[1]
      for i in range(2, len(cost)):
         dp[i] = cost[i] + min(dp[i-1], dp[i-2])
      return min(dp[-1], dp[-2])
ob = Solution()
print(ob.minCostClimbingStairs([12,17,20]))

इनपुट

[12,17,20]