304. Range Sum Query 2D - Immutable

Link

Solution

這題是考慮多次計算sum值的情況，所以用dp的方式把((0,0), (i,j))所有方形結果存起來之後就可以自由運用

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