寻找用 Python 绘制房屋的最低成本的程序
假设有一个大小为m的数组，代表一个小城市的m栋房子，每栋房子都必须涂上n种颜色中的一种（颜色从1到n标注），而且有些房子已经涂上了，所以不需要再画一次。有相同颜色的房屋称为邻里。我们有数组houses，其中houses[i]表示房子的颜色，如果颜色值为0，则表示房子还没有上色。我们有另一个称为成本的数组，这是一个二维数组，其中cost[i,j]表示用颜色j+1为房子i着色的成本。我们还有另一个名为target的输入值。我们必须找到粉刷所有剩余房屋所需的最低成本，以便精确地存在目标数量的社区。如果我们无法得到解决方案，则返回-1。
所以，如果输入是房子=[0,2,1,2,0]成本=[[1,10],[10,1],[10,1],[1,10],[5,1]]n=2target=3，那么输出会是11，因为有些房子已经画好了，所以我们要把房子画成[2,2,1,2,2]这样的，一共有三个邻域，[{2,2},{1},{2,2}]。粉刷第一个和最后一个房子的总成本(10+1)=11。
示例
让我们看下面的实现来更好地理解
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))输入
[0,2,1,2,0], [[1,10],[10,1],[10,1],[1,10],[5,1]], 2, 3输出结果
11