完整题目描述

题目：最小子矩阵

给定一个二维整数矩阵 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 示例代码

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 示例使用了四层循环，但内部使用了前缀和来优化子矩阵和的计算。对于大型矩阵，这种解法仍然可能较慢，但在面试场景下通常是可接受的。

码小课网站中有更多相关内容分享给大家学习，包括更高效的算法优化、更复杂的算法问题以及实际应用中的案例分析。