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

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

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

हल करने के चरण

• dp := cost के आकार का एक सरणी, 0 से भरा हुआ
• dp[0] := cost[0]
• यदि cost का आकार >= 2, तो:
  • dp[1] := cost[1]
• i को 2 से cost के आकार - 1 तक लूप करें:
  • dp[i] := cost[i] + min(dp[i-1], dp[i-2])
• min(dp[-1], dp[-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]

आउटपुट

17