Python straightforward DP solution

• No need to add additional columns or rows for edge cases. First, calculate the sum of the first row(matrix[0][0-n]) and the first column matrix[0-n][0], then start from matrix[1][1] to get all sums each from [0][0] to [i][j], then do some simple geometry calculation: s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+matrix[i][j], finally, we just need to get rid of the edge cases by simply check if i or j is less than zero.

``````class NumMatrix(object):
def __init__(self, matrix):
if not matrix: return
s=[[None for i in xrange(len(matrix[0]))] for j in xrange(len(matrix))]
s[0][0]=matrix[0][0]
for i in xrange(1,len(matrix[0])):
s[0][i]=matrix[0][i]+s[0][i-1]
for i in xrange(1,len(matrix)):
s[i][0]=matrix[i][0]+s[i-1][0]
for i in xrange(1,len(matrix)):
for j in xrange(1,len(matrix[0])):
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+matrix[i][j]
self.s=s

def sumRegion(self, row1, col1, row2, col2):
s=self.s
#edge cases checking
if row1-1<0:
s1=0
else:
s1=s[row1-1][col2]
if col1-1<0:
s2=0
else:
s2=s[row2][col1-1]
if row1-1<0 or col1-1<0:
s3=0
else:
s3=s[row1-1][col1-1]

return s[row2][col2]-s1-s2+s3``````

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