当前位置： 面试刷题>> 最小子矩阵 (经典算法题500道)
### 完整题目描述
**题目：最小子矩阵**
给定一个二维整数矩阵 `matrix`，要求找到该矩阵中的一个子矩阵（连续的子数组形成的矩形区域），使得子矩阵中的元素和最小，并返回这个最小和。
**注意**：
- 子矩阵的大小至少是 1x1。
- 你需要返回子矩阵的最小和，而不是子矩阵本身。
**示例 1**:
```
输入:
matrix = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
输出: 0
解释: 选中的子矩阵是 [1, 0, 1]，其和为 0。
```
**示例 2**:
```
输入:
matrix = [
[2, 2, 2],
[5, 5, 5],
[4, 4, 4]
]
输出: 8
解释: 选中的子矩阵是 [2, 2]，其和为 8。
```
### 解题思路
这个问题可以通过两层循环遍历所有可能的子矩阵，并使用另一层循环计算每个子矩阵的和。但是，这种方法的时间复杂度会非常高，达到 O(n^4)。
一个更优的解法是利用前缀和（Prefix Sum）和动态规划的思想，将计算子矩阵和的时间复杂度降低到 O(1)，从而将整体的时间复杂度降低到 O(n^3)。
1. **计算前缀和**：首先，计算原矩阵的每个位置 (i, j) 的前缀和 `prefixSum[i][j]`，它表示从 `(0, 0)` 到 `(i, j)` 的矩形区域内所有元素的和。
2. **遍历子矩阵**：然后，遍历所有可能的子矩阵的左上角 `(row1, col1)` 和右下角 `(row2, col2)`，利用前缀和快速计算出该子矩阵的和。
3. **记录最小和**：在遍历过程中，记录遇到的最小和。
### PHP 示例代码
```php
function minSubmatrixSum(array $matrix): int {
$rows = count($matrix);
$cols = count($matrix[0]);
$prefixSum = array_fill(0, $rows + 1, array_fill(0, $cols + 1, 0));
// 计算前缀和
for ($i = 1; $i <= $rows; $i++) {
for ($j = 1; $j <= $cols; $j++) {
$prefixSum[$i][$j] = $prefixSum[$i - 1][$j] + $prefixSum[$i][$j - 1] - $prefixSum[$i - 1][$j - 1] + $matrix[$i - 1][$j - 1];
}
}
$minSum = PHP_INT_MAX;
// 遍历所有可能的子矩阵
for ($row1 = 1; $row1 <= $rows; $row1++) {
for ($row2 = $row1; $row2 <= $rows; $row2++) {
for ($col1 = 1; $col1 <= $cols; $col1++) {
for ($col2 = $col1; $col2 <= $cols; $col2++) {
$sum = $prefixSum[$row2][$col2] - $prefixSum[$row1 - 1][$col2] - $prefixSum[$row2][$col1 - 1] + $prefixSum[$row1 - 1][$col1 - 1];
$minSum = min($minSum, $sum);
}
}
}
}
return $minSum;
}
```
请注意，这个 PHP 示例使用了四层循环，但内部使用了前缀和来优化子矩阵和的计算。对于大型矩阵，这种解法仍然可能较慢，但在面试场景下通常是可接受的。
**码小课网站中有更多相关内容分享给大家学习**，包括更高效的算法优化、更复杂的算法问题以及实际应用中的案例分析。