本文共 1805 字，大约阅读时间需要 6 分钟。
为了高效计算二维矩阵的子矩阵区域和，我们采用动态规划的方法。具体步骤如下：
动态规划数组初始化：创建一个dp数组，其中dp[r][c]表示第r行前c列的元素之和。该数组的大小为matrix.length行，matrix[0].length+1列。
预处理每一行：遍历矩阵中的每一行，逐列计算前缀和，并填充到dp数组中。例如，dp[r][c] = dp[r][c-1] + matrix[r][c-1]（假设c从1开始）。
计算子矩阵和：使用dp数组快速计算子矩阵的和。对于每一行，从col1到col2的范围内的和为dp[row][col2+1] - dp[row][col1]。将所有行的和累加即可。
以下是优化后的详细解释和代码：
详细解释
动态规划的核心思想是预先计算每一行的前缀和，从而在需要查询子矩阵和时，能够快速得到结果。具体步骤如下：
初始化dp数组：创建一个与原始矩阵同样行数的dp数组，其中每一行有matrix[0].length+1个元素。dp[r][0]初始化为0，表示前0列的和。
填充dp数组：对于每一行，遍历每一列，并更新dp[r][c]为当前行前c列的和。公式为：dp[r][c] = dp[r][c-1] + matrix[r][c-1]。
查询子矩阵和：对于给定的子矩阵范围，遍历从row1到row2的每一行，计算该行在col1到col2范围内的和。和的计算公式为：dp[row][col2+1] - dp[row][col1]。将所有行的结果累加，得到最终的子矩阵和。
这种方法的时间复杂度为O(rowscols)（预处理）和O(rows(cols))（查询），效率较高。
代码示例
class NumMatrix { private int[][] dp; public NumMatrix(int[][] matrix) { if (matrix.length == 0 || matrix[0].length == 0) return; int rows = matrix.length; int cols = matrix[0].length; dp = new int[rows][cols + 1]; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { dp[r][c + 1] = dp[r][c] + matrix[r][c]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for (int row = row1; row <= row2; row++) { sum += dp[row][col2 + 1] - dp[row][col1]; } return sum; }} 使用说明
初始化对象：创建NumMatrix对象，传入原始矩阵。
NumMatrix obj = new NumMatrix(matrix);
查询子矩阵和：调用sumRegion方法，传入子矩阵的左上角和右下角坐标。
int result = obj.sumRegion(row1, col1, row2, col2);
示例验证
假设矩阵为：
3 0 1 4 25 6 3 2 11 2 0 1 54 1 0 1 71 0 3 0 5
sumRegion(2, 1, 4, 3)：计算行2到4，列1到3的和。- 行2：dp[2][4] - dp[2][1] = 5 - 3 = 2
- 行3：dp[3][4] - dp[3][1] = 7 - 5 = 2
- 行4：dp[4][4] - dp[4][1] = 5 - 1 = 4
- 总和：2 + 2 + 4 = 8
其他示例同理，结果正确。
总结
通过动态规划预处理每一行的前缀和，我们可以在常数时间内查询任意子矩阵的和，显著提高了效率。这种方法在处理大规模矩阵时尤为有效。
发表评论
最新留言
关于作者
