उन पेड़ों की ऊंचाई बढ़ाने के लिए न्यूनतम लागत खोजने का कार्यक्रम जहां कोई भी आसन्न पेड़ पायथन में समान ऊंचाई नहीं रखता है

मान लीजिए कि हमारे पास ऊंचाई नामक संख्याओं की एक सूची है जो पौधों की ऊंचाई का प्रतिनिधित्व करती है और हमारे पास मूल्यों की एक और सूची है जिसे लागत कहा जाता है जो एक पौधे की ऊंचाई बढ़ाने के लिए आवश्यक मूल्य का प्रतिनिधित्व करता है। ऊंचाई सूची में प्रत्येक ऊंचाई को आसन्न ऊंचाई से अलग बनाने के लिए हमें सबसे छोटी लागत का पता लगाना होगा।

इसलिए, यदि इनपुट हाइट्स =[3, 2, 2] लागत =[2, 5, 3] जैसा है, तो आउटपुट 3 होगा, क्योंकि हम अंतिम ऊंचाई को 1 से बढ़ा सकते हैं, जिसकी लागत 3 है।

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

• एक फ़ंक्शन को परिभाषित करें dp() । इसमें idx, l_height

  . लगेगा

• अगर idx ऊंचाई -1 के आकार के समान है, तो

  • वापसी 0 यदि ऊँचाई [idx] l_height के समान नहीं है अन्यथा लागत [idx]

• रिट :=inf

• मेरे लिए 0 से 2 की सीमा में, करें

  • अगर ऊंचाई [idx] + i l_height के समान नहीं है, तो

    • रिट:=न्यूनतम रिट, डीपी (आईडीएक्स + 1, ऊंचाई [आईडीएक्स] + आई) + लागत [आईडीएक्स] * i

• वापसी रिट

• मुख्य विधि से वापसी dp(0, null)

उदाहरण

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

class Solution:
   def solve(self, heights, costs):
      def dp(idx, l_height):
         if idx == len(heights) - 1:
            return 0 if heights[idx] != l_height else costs[idx]
         ret = float("inf")
         for i in range(3):
            if heights[idx] + i != l_height:
               ret = min(ret, dp(idx + 1, heights[idx] + i) + costs[idx] * i)
         return ret
      return dp(0, None)
ob = Solution()
heights = [3, 2, 2]
costs = [2, 5, 3]
print(ob.solve(heights, costs))

इनपुट

[3, 2, 2], [2, 5, 3]

आउटपुट

3