資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
