在Python中找到用k种不同颜色粉刷栅栏的最小费用程序

在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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程