Chương trình tìm số coin tối đa thu được trên lưới di chuyển phải/xuống trong Python

Cho ma trận 2D mỗi ô chứa số coin. Bắt đầu từ (0,0), chỉ đi phải hoặc xuống. Tìm tổng coin tối đa đến góc dưới bên phải.

Ví dụ

Đầu vào: [[1,4,2,2],[6,0,0,5]].
Đầu ra: 14 (đường đi: 1,4,2,2,5).

Thuật toán

1. Cập nhật cột đầu: A[r][0] += A[r-1][0].
2. Cập nhật hàng đầu: A[0][c] += A[0][c-1].
3. Với các ô còn lại: A[r][c] += max(A[r-1][c], A[r][c-1]).
4. Trả về A[-1][-1].

Mã nguồn Python

class Solution:
    def solve(self, A):
        for r in range(1, len(A)):
            A[r][0] += A[r-1][0]
        for c in range(1, len(A[0])):
            A[0][c] += A[0][c-1]
        for r in range(1, len(A)):
            for c in range(1, len(A[0])):
                A[r][c] += max(A[r-1][c], A[r][c-1])
        return A[-1][-1]

ob = Solution()
matrix = [[1,4,2,2],[6,0,0,5]]
print(ob.solve(matrix))

Đầu vào / Đầu ra

Input: matrix = [[1,4,2,2],[6,0,0,5]]
Output: 14