[Leetcode] 304. Range Sum Query 2D - Immutable

https://leetcode.com/problems/range-sum-query-2d-immutable/description/
这道题是上一道题的升级版http://xuezha.blogspot.ca/2017/08/leetcode303-range-sum-query-immutable.html 

数组变成了二维数组，要求几乎一样。左上到右下，可以确定一个方块，把他们的和加起来。于是，我以左上为坐标零点，然后出发，到每一格，求他到坐标零点围成的方块的值。这个值就是当前格左边和上面的和减去左上角的数值。因为左上角的数值我们加了两次，在左边值和上面值里都有。

这个二维数组建好了之后呢，求和就是右下角的大方块到原点的值，减去上边界大方块，减去左边界大方块，加上左上方块。自己把思路写出来都觉得好复杂，看来真的有可以优化的地方。有重复计算。

我自己写的AC代码，虽然不好看吧，但是思路清晰。然而，时间很长。

class NumMatrix {

    int[][] n;
    public NumMatrix(int[][] matrix) {

        if(matrix != null && matrix.length !=0){
            n = new int[matrix.length][matrix[0].length];
            n = matrix;
            n[0][0] = matrix[0][0];
            for(int i=0; i<matrix.length; i++){
                for(int j=0; j<matrix[0].length; j++){
                    if(i==0){
                        if(j==0){
                            continue;
                        }
                        n[i][j] = n[i][j-1] + n[i][j];
                        continue;
                    }
                    if(j==0){
                        n[i][j] = n[i-1][j] + n[i][j];
                        continue;
                    }
                    n[i][j] = n[i][j] + n[i][j-1] + n[i-1][j] - n[i-1][j-1];
                }
            }
            //PrintInfo();
        }
    }
    
    public void PrintInfo(){
        for(int i=0; i<n.length; i++){
            for(int j=0; j<n.length; j++){
                System.out.println(i+", "+ j + ": " + n[i][j]);
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1 == 0 || col1 == 0){
            if(row1 == 0 && col1 == 0){
                return n[row2][col2];
            }
            if(row1 == 0){
                return n[row2][col2] - n[row2][col1-1];
            }
            if(col1 == 0){
                return n[row2][col2] - n[row1-1][col2];
            }
        }    
        return n[row2][col2] - n[row1-1][col2]-n[row2][col1-1] + n[row1-1][col1-1];
    }
}

然后我们来看一下击败90%的代码，膜拜一下：

public class NumMatrix {
    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 i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] + matrix[i][j] - dp[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];
    }
}

确实简洁，连我的n多边界条件都省略了。但是你仔细看，他的思路和我的一毛一样。大概都是先建立好一个数组，也是左上为原点。左边加上边的和，加matrix自己点的值，减去多加了的部分。但是我特别费事的加了一堆边界条件，就是怕-1的时候出错，冉家没有-1，全是+1，因为他多用了一行一列，然而那多出来的一行一列，默认初始就是0，所以对结果没影响。高，实在是高！