在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