线性动态规划：统计子矩阵中目标矩阵的最大和

题目描述

给定一个 m × n 的整数矩阵 matrix 和一个 r × c 的整数目标矩阵 target。
你可以从 matrix 中取出一个 r × c 的子矩阵（必须连续的行和列），我们希望这个子矩阵的所有元素之和尽可能接近 target 矩阵的元素之和。

具体定义“接近”为：
设子矩阵的元素之和为 sum_sub，目标矩阵元素之和为 sum_target，我们希望 |sum_sub − sum_target| 最小。

在保证差值最小的前提下，还要求这样的子矩阵个数最少。
最终我们需要返回这个最小的差值，并说明如何求解满足该最小差值的子矩阵个数。

解题思路

这是一个二维动态规划与前缀和优化结合的问题。
主要步骤：

1. 计算目标矩阵的和 sum_target。
2. 用前缀和快速求出 matrix 中任意子矩阵的和。
3. 枚举所有 r × c 的子矩阵，计算与目标和的差值，并记录。
4. 在动态规划时，注意要记录满足最小差值的子矩阵个数。

详细步骤

步骤1：计算目标矩阵的和

很简单：

sum_target = 所有 target[i][j] 的和

步骤2：预处理矩阵前缀和

设 prefix[i][j] 表示原矩阵从 (1,1) 到 (i,j) 的子矩阵和（1‑based 索引更方便）。
公式：

prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

其中 matrix 是 0‑based 索引。

有了前缀和，可以在 O(1) 时间计算任意子矩阵 (x1,y1) 到 (x2,y2) 的和：

sum_sub = prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1]

注意这里 x1, y1 是 0‑based 的起始行列，x2, y1 是 0‑based 的结束行列，且 x2 = x1 + r - 1, y2 = y1 + c - 1，且必须保证不越界。

步骤3：枚举所有 r×c 子矩阵

用两层循环枚举起始行 i 和起始列 j：

• 子矩阵范围：行 [i, i+r-1]，列 [j, j+c-1]
• 必须满足 i+r-1 < m 且 j+c-1 < n。

用前缀和公式求 sum_sub。
计算差值 diff = abs(sum_sub - sum_target)。

步骤4：动态规划思想记录最优解

我们可以在枚举的同时记录：

• min_diff：当前看到的最小差值。
• count：达到 min_diff 的子矩阵个数。

伪代码：

min_diff = INF
count = 0
for i from 0 to m-r:
    for j from 0 to n-c:
        sum_sub = 用前缀和公式计算
        diff = abs(sum_sub - sum_target)
        if diff < min_diff:
            min_diff = diff
            count = 1
        else if diff == min_diff:
            count += 1

最终返回 min_diff 和 count。

步骤5：时间复杂度分析

• 前缀和计算：O(mn)
• 枚举子矩阵：O((m-r+1)*(n-c+1)) ≈ O(mn) 当 r,c 不太小
• 每次计算和 O(1)
  总体 O(mn)，满足较大数据。

示例

例：

matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
r = 2, c = 2
target = [
  [1, 1],
  [1, 1]
]

1. sum_target = 4
2. 枚举所有 2×2 子矩阵：

• 左上角 (0,0)：和 = 1+2+4+5 = 12，diff = 8
• (0,1)：2+3+5+6=16，diff=12
• (1,0)：4+5+7+8=24，diff=20
• (1,1)：5+6+8+9=28，diff=24

最小 diff = 8，个数 = 1。

扩展讨论

如果题目要求差值最小且 sum_sub 最大（在 diff 相同时），只需在判断时增加条件即可。
如果矩阵元素有负数，方法依然适用。
如果允许子矩阵尺寸不固定，则变为更复杂的二维最大子矩阵和问题，可用动态规划 + 压缩行方法。