Chương trình tìm số tiền xu tối đa từ góc trên trái đến góc dưới phải và quay lại trong Python

Cho ma trận 2D với 3 giá trị: 0 (ô trống), 1 (tiền xu), -1 (tường). Từ góc trên trái (0,0) đi đến góc dưới phải (n-1,m-1) chỉ đi xuống hoặc sang phải, sau đó quay lại chỉ đi lên hoặc sang trái. Khi nhặt tiền xu ô đó thành 0. Tìm tối đa tiền xu thu được. Nếu không đến được đích trả về 0.

Ví dụ ma trận 4x3 cho kết quả 8.

Giải pháp

Quy hoạch động trên hai đường đi đồng thời (từ (0,0) đến (n-1,m-1)):

• util(i, j, k, l): tối đa tiền xu từ (0,0) đến (i,j) và (k,l) đồng thời
• Cả hai đường đi cùng bước (i+j == k+l), chỉ đi xuống/sang phải
• Nếu (i,j) == (k,l) chỉ tính tiền xu một lần
• Chuyển trạng thái từ 4 tổ hợp: (i-1,j)/(k-1,l), (i-1,j)/(k,l-1), (i,j-1)/(k-1,l), (i,j-1)/(k,l-1)

Ví dụ minh họa

class Solution:
    def solve(self, mat):
        n, m = len(mat), len(mat[0])
        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))

Đầu vào

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

Đầu ra

8