โปรแกรมหาต้นทุนขั้นต่ำในการทาสีรั้ว K สีใน Python

มีรั้ว N ต้น ต้องทาสีด้วย K สี โดย รั้วติดกันต้องไม่มีสีเหมือนกัน ให้เมทริกซ์ N×K ที่ cost[i][j] = ต้นทุนทารั้ว i ด้วยสี j หาต้นทุนรวมน้อยที่สุด

ตัวอย่าง

6 4 5
3 2 7
3 4 5
5 4 4

Output: 14 (เลือกสี index: 1→1→2→1 หรือ 5→2→3→4 ตามโจทย์)

แนวทางแก้ปัญหา

ใช้ DP แบบ Optimized O(N×K) โดยเก็บแค่ สีที่ถูกที่สุด (first) และ สองที่ถูกที่สุด (second) ของแถวก่อนหน้า:

1. สำหรับแต่ละแถว (รั้ว) คำนวณต้นทุนสำหรับแต่ละสี:
   • ถ้าเลือกสีเดียวกับ first ก่อนหน้า → ใช้ second ก่อนหน้า
   • มิฉะนั้น → ใช้ first ก่อนหน้า
2. อัปเดต first และ second ของแถวปัจจุบัน
3. คำตอบคือ first ของแถวสุดท้าย

การใช้งาน (Python)

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        fc, ft = 0, 0      # first color, first total
        sc, st = 1, 0      # second color, second total
        INF = 10**18
        
        for row in matrix:
            nfc, nft = -1, INF
            nsc, nst = -1, INF
            
            for i, cost in enumerate(row):
                # ใช้ first ก่อนหน้า ถ้าสีต่างกัน มิฉะนั้นใช้ second
                prev = ft if i != fc else st
                ct = cost + prev
                
                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))  # Output: 14

ความซับซ้อน

• Time Complexity: O(N × K)
• Space Complexity: O(1)