在Python中查找油漆房屋的最小成本的程序

假设有一个大小为m的数组，表示小城市中的m个房屋，每个房屋必须用n种颜色之一（颜色标号从1到n），并且某些房屋已经被粉刷过了，因此不需要再次进行粉刷。用同一种颜色涂色的房屋被称为邻居。我们有houses数组，其中houses [i]表示房屋的颜色，如果颜色值为0，则表示房屋尚未着色。我们还有另一个称为costs的数组，这是一个二维数组，其中costs [i，j]表示涂漆房屋i为颜色j + 1的成本。我们还有另一个输入值称为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：=几个房子

• 定义帮助器函数。这将取i，p_col，grp

• 如果i与m相同，则

  • 如果grp与target相同，则返回0，否则返回inf
• 如果houses [i]与0不同，则
  • 返回helper（i + 1，houses [i]，grp +（1 if p_col与houses [i]不同，否则为0）
• 总计：= inf

• 对于范围在1到n之间的col，做

  • total =最小的总和（cost [i，col-1] + helper（i + 1，col，grp +（1 when 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