โปรแกรมหาต้นทุนต่ำสุดเพิ่มความสูงต้นไม้ไม่ให้ติดกันเท่ากันใน Python

คำอธิบายโจทย์

ให้ heights = ความสูงต้นไม้, costs = ราคาเพิ่มความสูง 1 หน่วย หาต้นทุนน้อยที่สุดทำให้ต้นไม้ติดกันไม่มีความสูงเท่ากัน

ตัวอย่าง

heights = [3, 2, 2], costs = [2, 5, 3] → 3 (เพิ่มต้นสุดท้าย 1 หน่วย ค่า 3)

วิธีแก้ปัญหา

DP + Memoization:

1. dp(idx, left_height) = cost น้อยที่สุดจาก idx ถึงสุด โดยต้นไม้ idx-1 มีความสูง left_height
2. ลองเพิ่มความสูง idx 0, 1, 2 หน่วย (พอเพียงเพราะต้อง ≠ left_height)
3. ถ้า heights[idx] + i ≠ left_height: dp = min(dp, dp(idx+1, heights[idx]+i) + costs[idx]×i)
4. Base case: idx = n-1 → 0 ถ้า ≠ left_height ไม่อย่างนั้น costs[idx]

โค้ด Python

class Solution:
    def solve(self, heights, costs):
        from functools import lru_cache
        
        @lru_cache(None)
        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