304. Range Sum Query 2D – Immutable

Description

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D


The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Solution

At glance the description, we can point out that it’s can be solved by dp.

我们可以很容易的发现,这道题可以用动态规划解决。

Let’s fill the 4 key point in dynamic programming。

我们看看一下动态规划的4个要素。

Definition

dp[i][j] represent the sum from matrix’s upper left corner (0, 0) to matrix’s lower right (i, j)

Function

dp[i][j] = dp[i-1][j] + dp[i][j-1] – dp[i-1][j-1] + matrix[i][j]

Initialize

dp[0][0] = matrix[0][0]

dp[0][1] = matrix[0][0] + matrix[0][1]

dp[1][0] = matrix[0][0] + matrix[1][0]

Answer

dp[row2][col2] – dp[row1 – 1][col1 – 1] + dp[row1 – 1][col2] + dp[row2][col2 – 1]

Besides, to make solution more simple, we contruct the array dp[m + 1][n + 1]. In this way, we can avoid the edge case checking.

为了使代码更简洁,我们把dp数组初始化成m+1, n+1的形式。这样可以避免繁杂的初始化以及边界检查。

And we can hava the following code

得到如下代码

Java Time: O(mn), Space: O(mn)

class NumMatrix {
    int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return;
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] + dp[row1][col1] - dp[row1][col2 + 1] - dp[row2 + 1][col1];
    }
}

Python Time: O(mn), Space: O(mn)

class NumMatrix(object):

    def __init__(self, matrix):
        if matrix is None or not matrix:
            return
        m, n = len(matrix), len(matrix[0])
        dp = [[0 for j in xrange(n + 1)] for i in xrange(m + 1)]
        for i in xrange(1, m + 1):
            for j in xrange(1, n + 1):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1]

        self.dp = dp


    def sumRegion(self, row1, col1, row2, col2):
        return self.dp[row2 + 1][col2 + 1] + self.dp[row1][col1] - self.dp[row1][col2 + 1] - self.dp[row2 + 1][col1]

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号