程序以Python找出用k种不同颜色绘制栅栏的最低成本
假设我们要用K种不同的颜色绘制N条栅栏的行。我们希望将成本降到最低，同时确保没有两个相邻的围栏具有相同的颜色。因此，如果我们有一个NxK矩阵，其中第n行和第k列代表用第k种颜色绘制第n个栅栏的成本，则必须找到实现此目标的最低成本。
所以，如果输入像
则输出为14，因为我们可以选择以下颜色索引（从第一个栅栏开始）-5→2→3→4。
例
让我们看下面的实现以更好地理解-
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