304. Range Sum Query 2D - Immutable (Medium)

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).

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 1: DP

Sum(ABCD)=Sum(OD)−Sum(OB)−Sum(OC)+Sum(OA)

    private int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        dp = new int[matrix.length + 1][matrix[0].length + 1];
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
            }
        }
    }

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

改编：

1. 利特扣三零四改编-数1， 我以为是island结果听了题白高兴了，不是fb tag没做过, 瞎写了半天最后搞出来了但被指出两个index的bug.
2. 第二道给一个01矩阵，写一个接口，返回任意给定子矩阵里1的个数。交流中总算是写了出来。
3. 一个array里面只有1 和 0， query任何range里面的1的个数， presum秒了。array 换成 2d， range换成了矩形，李坑口上面原题。 这个要写的东西很多， 生成presum， query range。 最后省略变量定义等等， 写了core logic， 分析复杂度， 结束。