Problem statement

https://binarysearch.com/problems/Matrix-Prefix-Sum/

Solution

Just do what is asked, using dp.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, matrix):
        if not matrix: return []
        M, N = len(matrix), len(matrix[0])
        dp = [[0] * (N+1) for _ in range(M+1)] 
        for c, r in product(range(N), range(M)):
            dp[r+1][c+1] = dp[r+1][c] + dp[r][c+1] - dp[r][c] + matrix[r][c]
        return [row[1:] for row in dp[1:]]