Chương trình tìm chi phí tối thiểu tăng chiều cao cây trồng không cho cùng chiều cao liền kề trong Python

Cho danh sách heights (chiều cao cây) và costs (chi phí tăng 1 đơn vị). Tìm chi phí nhỏ nhất làm cho không có hai cây liền kề cùng chiều cao.

Ví dụ: heights=[3,2,2], costs=[2,5,3] → 3 (tăng cây cuối 1 đơn vị, chi phí 3).

Giải pháp

DP: dp(idx, l_height) = chi phí tối thiểu từ idx đến cuối, với cây trước có chiều cao l_height:

• Base case: idx == n-1: trả về 0 nếu heights[idx] != l_height else costs[idx]
• Thử tăng cây idx thêm 0, 1, hoặc 2 đơn vị (chỉ cần 3 trường hợp vì chỉ tránh bằng l_height)
• Nếu heights[idx] + i != l_height: ret = min(ret, dp(idx+1, heights[idx]+i) + costs[idx]*i)

Ví dụ minh họa

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))

Đầu vào

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

Đầu ra

3