Python DP solution in O(N^2) initialize and O(1) get range


  • 0
    A
    def __init__(self, matrix):
        n = len(matrix)
        if n == 0:
            self.dp = []
            return
        
        m = len(matrix[0])
    
        self.dp = [[0] * (m+1)]
        for i in xrange(n):
            self.dp.append([0] + matrix[i][:])
        
        self.dp[1][1:] = matrix[0][:]
        for i in xrange(1, n+1):
            for j in xrange(2, m+1):
                self.dp[i][j] += self.dp[i][j-1]
    
        for i in xrange(1, n+1):
            for j in xrange(1, m+1):
                self.dp[i][j] += self.dp[i-1][j]
    
    def sumRegion(self, row1, col1, row2, col2):
        if not self.dp:
            return 0
        return self.dp[row2+1][col2+1] - self.dp[row2+1][col1] - self.dp[row1][col2+1] + self.dp[row1][col1]

Log in to reply
 

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