题目

给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。

返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵的数目。

示例 1：

输入：grid = [[7,6,3],[6,6,1]], k = 18 输出：4 解释：如上图所示，只有 4 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 18 。

示例 2：

输入：grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20 输出：6 解释：如上图所示，只有 6 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 20 。

提示：

m == grid.length
n == grid[i].length
1 <= n, m <= 1000
0 <= grid[i][j] <= 1000
1 <= k <= 10^9

解题思路

这道题的核心是二维前缀和（2D Prefix Sum）与容斥原理的应用。

题目要求统计所有以 $(0, 0)$ 为左上角、且元素总和小于或等于 $k$ 的子矩阵数量。如果对每个子矩阵都重新遍历求和，时间复杂度会非常高。二维前缀和的作用是通过预处理，在 $O(1)$ 的时间内得出任意左上角固定子矩阵的元素总和。

以下是具体的解题逻辑：

1. 状态定义

定义一个二维数组 $dp$，其中 $dp[i+1][j+1]$ 表示原矩阵 grid 中以 $(0, 0)$ 为左上角、以 $(i, j)$ 为右下角的子矩阵的元素总和。

2. 状态转移方程

为了计算当前子矩阵的总和，我们需要利用已计算的相邻子矩阵的结果，避免重复计算。根据容斥原理，状态转移方程为：

$$dp[i+1][j+1] = grid[i][j] + dp[i][j+1] + dp[i+1][j] - dp[i][j]$$

公式项解析：

$grid[i][j]$：原矩阵当前坐标的元素值。
$dp[i][j+1]$：当前元素上方相邻的子矩阵总和。
$dp[i+1][j]$：当前元素左侧相邻的子矩阵总和。
$- dp[i][j]$：上方和左侧子矩阵的交集部分。因为在相加时该区域被计算了两次，所以需要减去一次。

3. 边界条件处理

原矩阵 grid 的尺寸为 $m \times n$。在计算 $i = 0$ 或 $j = 0$（即原矩阵的第一行或第一列）时，公式中的 $i-1$ 或 $j-1$ 会导致数组下标越界。

为了处理这个问题，初始化一个尺寸为 $(m+1) \times (n+1)$ 的 $dp$ 数组，并将所有元素默认置为 0。

$dp$ 数组的第 0 行和第 0 列作为计算时的基准零值，不对应 grid 中的实际元素。
grid 中的坐标 $(i, j)$ 严格映射到 $dp$ 数组中的 $(i+1, j+1)$。

4. 单调性与剪枝

题目给定 $grid[i][j] \ge 0$。根据这一条件，随着列索引 $j$ 的增加，子矩阵的面积扩大，其元素总和 $dp[i+1][j+1]$ 是单调非递减的。

在遍历第 $i$ 行时，如果判断出 $dp[i+1][j+1] > k$，则该行后续的所有列 $(j+2, j+3, \dots)$ 对应的前缀和必然也大于 $k$。
此时可以直接中断当前行的内层循环（break），跳至下一行继续计算，从而减少冗余的计算步骤。

具体代码

class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
        m = len(grid[0])
        n = len(grid)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        ans = 0

        for i in range(1, n+1):
            for j in range(1, m+1):
                dp[i][j] = grid[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
                if dp[i][j] <= k:
                    ans += 1
        return ans

impl Solution {
    pub fn count_submatrices(grid: Vec<Vec<i32>>, k: i32) -> i32 {

        let m = grid.len();
        let n = grid[0].len();

        let mut dp = vec![vec![0; n + 1]; m + 1];
        let mut ans = 0;

        for i in 1..=m {
            for j in 1..=n {
                dp[i][j] = grid[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
                if dp[i][j] > k {
                    break;
                } else {
                    ans += 1;
                }
            }
        }
        ans
    }
}

3070. 元素和小于等于 k 的子矩阵的数目

beautifulremi

题目