程序以Python找出用k种不同颜色绘制栅栏的最低成本

假设我们要用K种不同的颜色绘制N条栅栏的行。我们希望将成本降到最低，同时确保没有两个相邻的围栏具有相同的颜色。因此，如果我们有一个N x K矩阵，其中第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