Python simple DP solution

  • 0
    class NumMatrix(object):
    def __init__(self, matrix):
        initialize your data structure here.
        :type matrix: List[List[int]]
        if not matrix: 
            self.mat = []
        m,n = len(matrix), len(matrix[0])
        # def mat[r][c] := sum of (matrix[i][j]) i=[0..r], j=[0..c]
        self.mat = [[0 for i in xrange(n)] for j in xrange(m)] 
        for r in xrange(m):
            for c in xrange(n):
                self.mat[r][c] = matrix[r][c]
                if r-1>=0: self.mat[r][c] += self.mat[r-1][c]
                if c-1>=0: self.mat[r][c] += self.mat[r][c-1]
                if r-1>=0 and c-1>=0: self.mat[r][c] -= self.mat[r-1][c-1]
    def sumRegion(self, row1, col1, row2, col2):
        if not self.mat: return 0
        ret = self.mat[row2][col2]
        if row1-1>=0: ret -= self.mat[row1-1][col2]
        if col1-1>=0: ret -= self.mat[row2][col1-1]
        if row1-1>=0 and col1-1>=0: ret += self.mat[row1-1][col1-1]
        return ret

Log in to reply

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