Clean Java/Python dp solution


  • 0

    The problem is the same as 1D just slightly complicated.
    Whether or not we can reuse the matrix provided to store the dp results depends on the requirement.
    In practice I would rather use O(m*n) extra space to avoid mutate the given matrix.

    Java

    private int[][] sums;
    
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0)
            return;
        int m = matrix.length, n = matrix[0].length;
        sums = new int[m + 1][n + 1];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                sums[i + 1][j + 1] = matrix[i][j] - sums[i][j]
                             + sums[i][j + 1] + sums[i + 1][j];
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return    sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1]
                - sums[row2 + 1][col1] + sums[row1][col1];
    }
    

    Python

    def __init__(self, matrix):
        if not matrix:
            return
        self.sums = [[0] * (len(matrix[0]) + 1)]
        for row in matrix:
            stack = [0]
            for x in row:
                stack.append(stack[-1] + x)
            self.sums.append(map(sum, zip(self.sums[-1], stack)))
    
    def sumRegion(self, top, left, bottom, right):
        return self.sums[bottom + 1][right + 1] + self.sums[top][left] \
             - self.sums[top][right + 1] - self.sums[bottom + 1][left]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.