给定一个 N \times MN×M 的矩阵 AA，请你统计有多少个子矩阵 (最小 1 \times 11×1, 最大 N \times M)N×M) 满足子矩阵中所有数的和不超过给定的整数 KK。

这是一个经典的动态规划（Dynamic Programming）问题，通常可以通过使用二维数组来存储中间结果来解决。我们可以定义一个二维数组 dp[N+1][K+1]，其中 dp[i][j] 表示在一个大小为 i \times j i×j 的子矩阵中，元素之和最大为 j 时的情况数量。

算法步骤如下：

1. 初始化：dp[0][0] = 1，表示空矩阵（即没有元素）满足条件；对于其他元素，dp[i][0] 和 dp[0][j] 都设置为 0，因为至少有一个元素的和必须大于 0。

2. 计算过程：遍历矩阵 A 中的每个元素 a[i][j]，对于每个位置 (i, j)，更新 dp[i][j] 有两种情况：
- 如果我们不包含当前元素，则 dp[i][j] = dp[i-1][j]，因为不包括元素意味着上一行或同一行的某个列组合。
- 如果我们包含当前元素，则 dp[i][j] = dp[i-1][j-a[i][j]] + dp[i][j-a[i][j]]，因为我们有两选择：要么不包含这个元素，要么包含并减少总和。

3. 最终答案：我们需要找到所有和小于等于 K 的非空子矩阵的数量，这可以通过 dp[N][K] 得到。

下面是 C++ 代码实现：

#include <vector>

int countSubmatrices(vector<vector<int>>& matrix, int K) {
    int N = matrix.size(), M = matrix[0].size();
    vector<vector<int>> dp(N+1, vector<int>(K+1, 0));
    
    // 初始化
    for (int i = 1; i <= N; i++) {
        dp[i][0] = 1;
    }
    for (int j = 1; j <= K; j++) {
        dp[0][j] = 0;
    }

    // 动态规划计算
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            dp[i][j] = dp[i-1][j];
            if (matrix[i-1][j-1] <= K) {
                dp[i][j] += dp[i-1][j-matrix[i-1][j-1]];
            }
        }
    }

    return dp[N][K];
}