Chương trình tìm chi phí tối thiểu tô màu nhà trong Python

Cho m nhà, n màu (1..n). Mảng houses: houses[i] = màu đã tô (0 = chưa tô). Ma trận cost[i][j] = chi phí tô nhà i màu j+1. Yêu cầu: tô các nhà chưa màu sao cho có đúng target "khu lân cận" (đoạn liên tiếp cùng màu). Tìm chi phí nhỏ nhất, -1 nếu không thể.

Ví dụ: houses=[0,2,1,2,0], cost=[[1,10],[10,1],[10,1],[1,10],[5,1]], n=2, target=3 → 11. Tô thành [2,2,1,2,2]: 3 khu lân cận {2,2}, {1}, {2,2}. Chi phí = 10+1=11.

Giải thuật (Đệ quy + Memoization)

1. Hàm helper(i, p_col, grp): chi phí nhỏ nhất từ nhà i trở đi, màu trước p_col, đã có grp khu lân cận.
   • Nếu i == m: trả về 0 nếu grp == target else inf.
   • Nếu houses[i] != 0: đã có màu, gọi helper(i+1, houses[i], grp + (p_col != houses[i])).
   • Ngược lại: thử mọi màu col 1..n, lấy min của cost[i][col-1] + helper(i+1, col, grp + (p_col != col)).
2. Kết quả: ans = helper(0, -1, 0), trả về ans nếu ≠ inf else -1.

Ví dụ minh họa

def solve(houses, cost, n, target):
    m = len(houses)
    def helper(i, p_col, grp):
        if i == m:
            return 0 if grp == target else float('inf')
        if houses[i] != 0:
            return helper(i + 1, houses[i], grp + int(p_col != houses[i]))
        total = float('inf')
        for col in range(1, n + 1):
            total = min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col != col)))
        return total
    ans = helper(0, -1, 0)
    return ans if ans != float('inf') else -1

houses = [0,2,1,2,0]
cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]
n = 2
target = 3
print(solve(houses, cost, n, target))

Đầu vào

[0,2,1,2,0], [[1,10],[10,1],[10,1],[1,10],[5,1]], 2, 3

Đầu ra

11