資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢使用k種不同顏色粉刷柵欄的最小成本
假設我們要用K種不同的顏色粉刷N個柵欄。我們希望在確保沒有兩個相鄰柵欄顏色相同的情況下，使成本最小化。因此，如果我們有一個N x K矩陣，其中第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 := 無窮大
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] ]
輸出
14
更新於: 2020年12月22日
255次瀏覽
廣告