पायथन में k अलग-अलग रंगों से बाड़ रंगने की न्यूनतम लागत ज्ञात करने का प्रोग्राम

मान लीजिए हम N बाड़ों की एक पंक्ति को K अलग-अलग रंगों से रंगना चाहते हैं। हम लागत को न्यूनतम करना चाहते हैं जबकि यह सुनिश्चित करते हैं कि कोई भी दो पड़ोसी बाड़ एक ही रंग के न हों। यदि हमारे पास एक N x K मैट्रिक्स है जहां nवीं पंक्ति और kवां कॉलम nवीं बाड़ को kवें रंग से रंगने की लागत दर्शाता है, तो हमें न्यूनतम लागत ज्ञात करनी है जो इस लक्ष्य को प्राप्त करती है।

उदाहरण के लिए, यदि मैट्रिक्स है:

एल्गोरिदम (O(N*K) समय, O(1) स्पेस)

• प्रत्येक पंक्ति के लिए, न्यूनतम लागत (fc, ft) और दूसरी न्यूनतम लागत (sc, st) वाले रंग को ट्रैक करें
• अगली पंक्ति के लिए, प्रत्येक रंग के लिए लागत की गणना करें: यदि रंग पिछली न्यूनतम लागत वाले रंग से अलग है तो ft जोड़ें, अन्यथा st जोड़ें
• नई न्यूनतम और दूसरी न्यूनतम लागत अपडेट करें
• अंत में 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