Chương trình tìm số coin tối đa từ ma trận coin biến mất Python

Cho ma trận 2D, matrix[r][c] là số coin ở ô đó. Khi lấy coin tại (r,c), toàn bộ coin ở hàng r-1 và r+1 biến mất, cùng với coin tại (r,c-1) và (r,c+1). Tìm tổng coin tối đa có thể thu thập.

Ví dụ: ma trận 3x4 → kết quả 26 (chọn 8, 6, 9, 3).

Giải thuật (Quy hoạch động 2 lớp)

1. Hàm getmax(arr): tìm tổng lớn nhất của dãy con không chọn hai phần tử liền kề (House Robber)
2. Áp dụng getmax cho từng hàng → mảng row_sum
3. Áp dụng getmax cho row_sum → kết quả cuối cùng

Ví dụ triển khai

def getmax(arr):
    prev_max = curr_max = 0
    res = 0
    for num in arr:
        temp = curr_max
        curr_max = num + prev_max
        prev_max = max(temp, prev_max)
        res = max(res, curr_max)
    return res

def solve(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    row_sum = [0] * m
    for i in range(m):
        row_sum[i] = getmax(matrix[i])
    return getmax(row_sum)

matrix = [[2,8,7,6], [10,10,4,2], [5,9,2,3]]
print(solve(matrix))

Đầu vào

[[2,8,7,6], [10,10,4,2], [5,9,2,3]]

Đầu ra

26