Python程序：查找使用k种不同颜色粉刷栅栏的最小成本

假设我们要用K种不同的颜色粉刷N个栅栏。我们希望在确保没有两个相邻栅栏颜色相同的情况下，使成本最小化。因此，如果我们有一个N x K矩阵，其中第n行和第k列表示用第k种颜色粉刷第n个栅栏的成本，我们必须找到实现此目标的最小成本。

因此，如果输入类似于

645
327
345
544

则输出将为14，因为我们可以选择以下颜色索引（从第一个栅栏开始） - 5 → 2 → 3 → 4。

为了解决这个问题，我们将遵循以下步骤 -

  • n := 矩阵的行数

  • fc := 0, ft := 0

  • sc := 1, st := 0

  • 对于矩阵中的每一行，执行以下操作

    • nfc := -1, nft := 无穷大

    • nsc := -1, nst := 无穷大

    • 对于每一索引i和值t行，执行以下操作

      • ct := t +(如果i与fc不同则为ft，否则为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

示例

让我们看看以下实现以获得更好的理解 -

实时演示

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]
]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

14

更新于: 2020年12月22日

255次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告