在Python中找到用k种不同颜色粉刷栅栏的最小费用程序
假设我们想用K种不同的颜色粉刷N个栅栏。我们想要在确保没有相邻的栅栏颜色相同的同时最小化成本。因此,如果我们有一个NxK矩阵,其中第n行和第k列表示用第k种颜色粉刷第n个栅栏的成本,我们必须找到实现此目标的最小成本。
因此,如果输入如下:
6 | 4 | 5 |
---|---|---|
3 | 2 | 7 |
3 | 4 | 5 |
5 | 4 | 4 |
那么输出将是14,因为我们可以选择以下颜色索引(从第一个栅栏开始)-5→2→3→4。
要解决此问题,我们将按以下步骤进行-
- n:=矩阵的行数
- fc:=0,ft:=0
- sc:=1,st:=0
- 对于矩阵中的每一行,执行以下操作
- nfc:=-1,nft:=inf
- nsc:=-1,nst:=inf
- 对于行中的每个索引值t,执行以下操作
- ct:=t +(fc如果i与fc不同否则st)
- 如果ct <= nft,那么
- nsc:=nfc,nst:=nft
- nfc:=i,nft:=ct
- 否则当ct <= nst时,
- nsc:=i,nst:=ct
- fc:=nfc,ft:=nft
- sc:=nsc,st:=nst
- 返回ft
更多Python相关文章,请阅读:Python 教程
示例
让我们看一下以下实现以获得更好的理解:
class Solution:
def solve(self, matrix):
n = len(matrix)
fc, ft = 0, 0
sc, st = 1, 0
inf = int(1e18)
for row in matrix:
nfc, nft = -1, inf
nsc, nst = -1, inf
for i, t in enumerate(row):
ct = t + (ft if i != fc else st)
if ct <= nft:
nsc, nst = nfc, nft
nfc, nft =i, ct
elif ct <= nst:
nsc, nst = i, ct
fc, ft = nfc, nft
sc, st = nsc, nst
return ft
ob = Solution()
matrix = [
[6, 4, 5],
[3, 2, 7],
[3, 4, 5],
[5, 4, 4]
]
print(ob.solve(matrix))
输入
[
[6, 4, 5],
[3, 2, 7],
[3, 4, 5],
[5, 4, 4]
]
输出
14