পাইথনে কোন পার্শ্ববর্তী গাছের সমান উচ্চতা নেই এমন গাছের উচ্চতা বাড়ানোর জন্য ন্যূনতম খরচ খোঁজার প্রোগ্রাম

ধরুন আমাদের কাছে উচ্চতা নামক সংখ্যার একটি তালিকা রয়েছে যা গাছের উচ্চতাকে প্রতিনিধিত্ব করে এবং আমাদের কাছে খরচ নামে আরেকটি মানের তালিকা রয়েছে যা একটি গাছের উচ্চতা এক দ্বারা বাড়ানোর জন্য প্রয়োজনীয় মূল্যকে প্রতিনিধিত্ব করে। উচ্চতার তালিকায় প্রতিটি উচ্চতাকে সংলগ্ন উচ্চতা থেকে আলাদা করার জন্য আমাদের সবচেয়ে ছোট খরচ খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি উচ্চতা =[3, 2, 2] খরচ =[2, 5, 3] এর মত হয়, তাহলে আউটপুট 3 হবে, কারণ আমরা শেষ উচ্চতা 1 দ্বারা বাড়াতে পারি, যার দাম 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি idx, l_height

  লাগবে

• যদি idx উচ্চতার আকারের সমান হয় - 1, তাহলে

  • উচ্চতা[idx] l_height এর সমান না হলে 0 ফেরত দিন অন্যথায় খরচ[idx]

• ret :=inf

• আমি 0 থেকে 2 রেঞ্জের জন্য, কর

  • যদি উচ্চতা[idx] + i l_height এর সমান না হয়, তাহলে

    • ret :=ret, dp(idx + 1, heights[idx] + i) + খরচ[idx] * 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