Pythonでk個の異なる色でフェンスをペイントするための最小コストを見つけるためのプログラム

N個のフェンスの列をK個の異なる色でペイントするとします。隣接する2つのフェンスが同じ色にならないようにしながら、コストを最小限に抑えたいと考えています。したがって、n番目の行とk番目の列がk番目の色でn番目のフェンスをペイントするコストを表すN x Kマトリックスがある場合、この目標を達成するための最小コストを見つける必要があります。

したがって、入力が次のような場合

次のカラーインデックス（最初のフェンスから開始）を選択できるため、出力は14になります。-5→2→3→4。

これを解決するには、次の手順に従います-

• n：=行列の行数

• fc：=0、ft：=0

• sc：=1、st：=0

• 行列の各行について、次のようにします

  • nfc：=-1、nft：=inf

  • nsc：=-1、nst：=inf

  • インデックス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

• フィートを返す

例

理解を深めるために、次の実装を見てみましょう-

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