โปรแกรมหาเหรียญสูงสุดจากมุมซ้ายบนไปขวาล่างและกลับมาใน Python

คำอธิบายโจทย์

ให้เมทริกซ์ 2D ค่า: 0=ว่าง, 1=เหรียญ, -1=กำแพง เริ่มที่ (0,0) ไป (n-1,m-1) เดินขวา/ล่างเท่านั้น แล้วกลับมา (0,0) เดินซ้าย/บนเท่านั้น เหรียญเก็บได้ครั้งเดียว (เซลล์กลายเป็น 0) หาเหรียญสูงสุด ถ้าไปไม่ถึงปลายทางคืน 0

ตัวอย่าง

เมทริกซ์ 4x3 → เอาต์พุต: 8

วิธีแก้ปัญหา

มองว่าเป็น 2 คนเดินจาก (0,0) ไป (n-1,m-1) พร้อมกัน (คนละคน) เพื่อไม่ให้เก็บเหรียญซ้ำ:

1. DP state: util(i, j, k, l) = เหรียญสูงสุดเมื่อคน1อยู่(i,j) คน2อยู่(k,l) ทั้งคู่เดินจาก (0,0)
2. Transition: ทั้งคู่มาจากบนหรือซ้าย (4 รูปแบบ)
3. ถ้าทั้งคู่อยู่เซลล์เดียวกัน นับเหรียญครั้งเดียว
4. Base case: util(0,0,0,0) = mat[0][0]
5. คำตอบ: max(0, util(n-1,m-1,n-1,m-1))

โค้ด Python

class Solution:
    def solve(self, mat):
        n, m = len(mat), len(mat[0])
        
        from functools import lru_cache
        
        @lru_cache(None)
        def util(i, j, k, l):
            if not (0 <= i < n and 0 <= j < m) or mat[i][j] == -1:
                return -1e9
            if not (0 <= k < n and 0 <= l < m) or mat[k][l] == -1:
                return -1e9
            if i == 0 and j == 0 and k == 0 and l == 0:
                return mat[0][0]
            
            best = -1e9
            for dx1, dy1 in [(-1, 0), (0, -1)]:
                for dx2, dy2 in [(-1, 0), (0, -1)]:
                    best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
            
            return mat[i][j] + (i != k) * mat[k][l] + best
        
        return max(0, util(n - 1, m - 1, n - 1, m - 1))

ob = Solution()
matrix = [
    [0, 1, 1],
    [1, 1, 1],
    [1, -1, 1],
    [0, 1, 1]
]
print(ob.solve(matrix))

อินพุต

[[0, 1, 1], [1, 1, 1], [1, -1, 1], [0, 1, 1]]

เอาต์พุต

8