【LeetCode】Day62-矩阵区域和

1314. 矩阵区域和【中等】

从昨天的题开始，动态规划上二维啦！

这道题引出的一个概念-二维前缀和，大概意思如下图：

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m=mat.length,n=mat[0].length;
        int ans[][]=new int[m][n];
        int dp[][]=new int[m+1][n+1];
        //计算前缀和
        for(int i=0;i
            for(int j=0;j
                dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]-dp[i][j]+mat[i][j];
            }
        }
        //计算结果
        for(int i=0;i
            for(int j=0;j
                int top=Math.max(i-k,0),bottom=Math.min(i+k+1,m);
                int left=Math.max(j-k,0),right=Math.min(j+k+1,n);
                ans[i][j]=dp[bottom][right]-dp[bottom][left]-dp[top][right]+dp[top][left];
            }
        }
        return ans;
    }
}

时间复杂度： O ( m n ) O(mn) O(mn)

空间复杂度： O ( m n ) O(mn) O(mn)

304. 二维区域和检索 - 矩阵不可变【中等】

几乎和上一题一样

class NumMatrix {
    private int matrix[][];
    private int dp[][];
    public NumMatrix(int[][] matrix) {
        this.matrix=matrix;
        int m=matrix.length,n=matrix[0].length;
        //计算前缀和
        dp=new int[m+1][n+1];
        for(int i=0;i
            for(int j=0;j
                dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]-dp[i][j]+matrix[i][j];
            }
        }
    }
    
    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];
    }
}

时间复杂度： O ( m n ) O(mn) O(mn)

空间复杂度： O ( m n ) O(mn) O(mn)