পাইথনে গাছের উন্নতি খরচে আশেপাশের গাছের উচ্চতা ভিন্ন রাখার ন্যূনতম খরচ

একটি লিস্ট heights (গাছের উচ্চতা) এবং costs (প্রতি ইউনিট উচ্চতা বেড়ানোর খরচ) দেওয়া আছে। আশেপাশের দুটি গাছের উচ্চতা একই না হয় এমনভাবে ন্যূনতম খরচে উচ্চতা বেড়াতে হবে।

উদাহরণ: heights = [3, 2, 2], costs = [2, 5, 3] → আউটপুট 3 (শেষ গাছের উচ্চতা ১ বাড়াতে খরচ ৩)।

সমাধানের ধাপসমূহ (DP / মেমোরাইজেশন)

dp(idx, l_height) ফাংশন: idx-তম গাছ প্রসেস করা হচ্ছে, বাম পাশের গাছের Höhen l_height।
বেস কেস: লাস্ট গাছ হলে, যদি heights[idx] != l_height হয় তবে ০, অন্যথায় costs[idx] (১ ইউনিট বেড়াতে হবে)।
ret = inf। i = 0,1,2 (০, ১, ২ ইউনিট বেড়ানো) ট্রাই করুন।
যদি heights[idx] + i != l_height হয়, তবে ret = min(ret, dp(idx+1, heights[idx]+i) + costs[idx]*i)।
ret রিটার্ন করুন। মেইন থেকে dp(0, None) কল করুন।

পাইথন কোড উদাহরণ

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]