पायथन में पेड़ों की ऊंचाई बढ़ाने की न्यूनतम लागत जहां कोई आसन्न पेड़ समान ऊंचाई का न हो

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

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

हल करने के चरण

• dp() फ़ंक्शन परिभाषित करें। यह idx, l_height लेगा

  • यदि idx, heights के आकार - 1 के समान है, तो

    • 0 लौटाएं यदि heights[idx], l_height के समान नहीं है अन्यथा costs[idx]

  • ret := infinity

  • i के लिए 0 से 2 तक की रेंज में, करें

    • यदि heights[idx] + i, l_height के समान नहीं है, तो

      • ret := ret और dp(idx + 1, heights[idx] + i) + costs[idx] * i का न्यूनतम

  • ret लौटाएं

• मुख्य विधि से 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