# Clean Java/Python dp solution

• 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]``````

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