Chương trình tìm ma trận tổng tiền tố hàng và cột trong Python

Cho ma trận đầu vào, tìm ma trận kết quả cùng kích thước mà mỗi phần tử res[i][j] = tổng tất cả matrix[r][c] với r ≤ i và c ≤ j (tổng tiền tố 2D).

Ví dụ: đầu vào [[8,2],[7,4]] → kết quả [[8,10],[15,21]].

Thuật toán giải quyết (O(R×C))

1. Nếu ma trận rỗng: trả về ngay
2. Tính tổng tiền tố theo hàng: matrix[r][c] += matrix[r-1][c] cho r = 1..R-1
3. Tính tổng tiền tố theo cột: matrix[r][c] += matrix[r][c-1] cho c = 1..C-1
4. Trả về ma trận đã biến đổi

Ví dụ minh họa

def solve(matrix):
    if not matrix:
        return matrix
    R, C = len(matrix), len(matrix[0])
    for r in range(1, R):
        for c in range(C):
            matrix[r][c] += matrix[r-1][c]
    for r in range(R):
        for c in range(1, C):
            matrix[r][c] += matrix[r][c-1]
    return matrix

matrix = [[8, 2], [7, 4]]
print(solve(matrix))

Đầu vào

[[8, 2],[7, 4]]

Đầu ra

[[8, 10], [15, 21]]