用 Python 编写程序，查找粉刷房屋的最低成本
假设有一个大小为 m 的数组，表示一个小城市中的 m 栋房屋，每栋房屋必须涂上 n 种颜色中的一种(颜色从 1 到 n 标记)，有些房屋已经涂过漆，因此无需再次涂漆。涂上相同颜色的房屋称为邻域。我们有数组 houses，其中 houses[i] 表示房屋的颜色，如果颜色值为 0，则表示房屋尚未上漆。我们还有另一个数组称为 cost，这是一个二维数组，其中 cost[i, j] 表示将房屋 i 涂上颜色 j+1 的成本。我们还有另一个输入值称为 target。我们必须找到粉刷所有剩余房屋所需的最低成本，以便恰好有目标数量的邻域。如果无法得到解决方案，则返回 -1。
因此，如果输入为 houses = [0,2,1,2,0] cost = [[1,10],[10,1],[10,1],[1,10],[5,1]] n = 2 target = 3，则输出将为 11，因为有些房屋已经粉刷过了，因此我们必须以 [2,2,1,2,2] 这样的方式粉刷房屋，有三个街区，[{2,2}, {1}, {2,2}]。粉刷第一栋和最后一栋房屋的总成本 (10 + 1) = 11。
为了解决这个问题，我们将遵循以下步骤 −
m := 房屋大小
定义一个函数 helper() 。这将需要 i、p_col、grp
如果 i 与 m 相同，则
如果 grp 与 target 相同，则返回 0，否则为 inf
如果 houses[i] 不等于 0，则
如果 p_col 与 houses[i] 不同，则返回 helper(i + 1, houses[i], grp + (1，如果 p_col 与 houses[i] 不同，否则为 0)
total := inf
对于范围从 1 到 n 的 col，执行
total = total 和 (cost[i, col - 1] + helper(i + 1, col, grp + (1 当 p_col与 col 不同，否则为 0)))
返回总计
从主方法执行以下操作
ans := helper(0, -1, 0)
如果 ans 不是 inf，则返回 ans，否则返回 -1
示例
让我们看看下面的实现以便更好地理解
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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
