โปรแกรมหาเมทริกซ์ Prefix Sum 2D ใน Python

ให้เมทริกซ์ หาเมทริกซ์ใหม่ res[i][j] = ผลรวม matrix[r][c] สำหรับ r ≤ i, c ≤ j

ตัวอย่าง: [[8,2],[7,4]] → [[8,10],[15,21]]

ขั้นตอน (In-place 2-pass)

1. Prefix Sum แนวตั้ง: matrix[r][c] += matrix[r-1][c]
2. Prefix Sum แนวนอน: matrix[r][c] += matrix[r][c-1]
3. คืนค่าเมทริกซ์ที่แก้ไขแล้ว

ตัวอย่างโค้ด

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))  # Output: [[8, 10], [15, 21]]

อินพุต

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

เอาต์พุต

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