数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找房屋粉刷的最小成本
假设有一个大小为m的数组，表示一个小城市中的m栋房屋，每栋房屋必须用n种颜色之一进行粉刷（颜色从1到n编号），并且一些房屋已经粉刷过，因此无需再次粉刷。用相同颜色粉刷的房屋称为邻域。我们有数组houses，其中houses[i]表示房屋的颜色，如果颜色值为0，则表示房屋尚未粉刷。我们还有另一个名为costs的数组，这是一个二维数组，其中costs[i, j]表示用颜色j+1粉刷房屋i的成本。我们还有一个输入值target。我们必须找到粉刷所有剩余房屋所需的最小成本，使得正好有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 := houses的大小
定义一个函数helper()。它将接收i、p_col、grp作为参数。
如果i等于m，则
如果grp等于target，则返回0，否则返回inf
如果houses[i]不等于0，则
返回helper(i + 1, houses[i], grp + (如果p_col不等于houses[i]则为1，否则为0))
total := inf
对于col从1到n，执行以下操作
total = total和(cost[i, col - 1] + helper(i + 1, col, grp + (当p_col不等于col时为1，否则为0)))的最小值
返回total
从主方法执行以下操作
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
389 次查看
