最大正方形(动态规划)

Dear 丶 2023-03-12 12:25 6阅读 0赞

#### 最大正方形 ####

难度 中等

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

**示例:**

输入: 
    
    1 0 1 0 0
    1 0 1 1 1
    1 1 1 1 1
    1 0 0 1 0
    
    输出: 4

## 实现动态规划： ##

可以使用动态规划降低时间复杂度。我们用 dp(i, j) 表示以(i,j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。

那么如何计算 dp 中的每个元素值呢？对于每个位置 (i,j)，检查在矩阵中该位置的值：

如果该位置的值是 0，则 dp(i, j) = 0因为当前位置不可能在由 1 组成的正方形中；

如果该位置的值是 1，则dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1

此外，还需要考虑边界条件。如果 i 和 j 中至少有一个为 00，则以位置(i,j) 为右下角的最大正方形的边长只能是 1，因此dp(i,j)=1。

以下用一个例子具体说明。原始矩阵如下。

0 1 1 1 0
    1 1 1 1 0
    0 1 1 1 1
    0 1 1 1 1
    0 0 1 1 1

对应的 dpdp 值如下。

0 1 1 1 0
    1 1 2 2 0
    0 1 2 3 1
    0 1 2 3 2
    0 0 1 2 3

下图也给出了计算 dp 值的过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bmZlbmdmZW5nZmVuZw_size_16_color_FFFFFF_t_70]

class Solution { 
        public int maximalSquare(char[][] matrix) { 
            int maxSide = 0;
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { 
                return maxSide;
            }
            int rows = matrix.length, columns = matrix[0].length;
            int[][] dp = new int[rows][columns];
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < columns; j++) { 
                    if (matrix[i][j] == '1') { 
                        if (i == 0 || j == 0) { 
                            dp[i][j] = 1;
                        } else { 
                            dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                        }
                        maxSide = Math.max(maxSide, dp[i][j]);
                    }
                }
            }
            int maxSquare = maxSide * maxSide;
            return maxSquare;
        }
    }

## 复杂度分析 ##

时间复杂度：O(mn)其中 m 和 n是矩阵的行数和列数。需要遍历原始矩阵中的每个元素计算 dp 的值。

空间复杂度：O(mn)，其中 m 和 n 是矩阵的行数和列数。创建了一个和原始矩阵大小相同的矩阵 dp。由于状态转移方程中的dp(i,j) 由其上方、左方和左上方的三个相邻位置的 dp 值决定，因此可以使用两个一维数组进行状态转移，空间复杂度优化至 O(n)

## 状态转移公式推导： ##

我们用 f\[i\]\[j\] 表示以 (i, j) 为右下角的正方形的最大边长，那么除此定义之外，f\[i\]\[j\] = x 也表示以 (i, j) 为右下角的正方形的数目为 x（即边长为 1, 2, …, x 的正方形各一个）。在计算出所有的 f\[i\]\[j\] 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。

我们尝试挖掘 f\[i\]\[j\] 与相邻位置的关系来计算出 f\[i\]\[j\] 的值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bmZlbmdmZW5nZmVuZw_size_16_color_FFFFFF_t_70 1]  
如上图所示，若对于位置 (i, j) 有 f\[i\]\[j\] = 4，我们将以 (i, j) 为右下角、边长为 4 的正方形涂上色，可以发现其左侧位置 (i, j - 1)，上方位置 (i - 1, j) 和左上位置 (i - 1, j - 1) 均可以作为一个边长为 4 - 1 = 3 的正方形的右下角。也就是说，这些位置的的 f 值至少为 3，即：

f[i][j - 1] >= f[i][j] - 1
    f[i - 1][j] >= f[i][j] - 1
    f[i - 1][j - 1] >= f[i][j] - 1

将这三个不等式联立，可以得到：

min(f[i][j−1],f[i−1][j],f[i−1][j−1])≥f[i][j]−1

这是我们通过固定 f\[i\]\[j\] 的值，判断其相邻位置与之的关系得到的不等式。同理，我们也可以固定 f\[i\]\[j\] 相邻位置的值，得到另外的限制条件。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bmZlbmdmZW5nZmVuZw_size_16_color_FFFFFF_t_70 2]  
如上图所示，假设 f\[i\]\[j - 1\]，f\[i - 1\]\[j\] 和 f\[i - 1\]\[j - 1\] 中的最小值为 3，也就是说，(i, j - 1)，(i - 1, j) 和 (i - 1, j - 1) 均可以作为一个边长为 3 的正方形的右下角。我们将这些边长为 3 的正方形依次涂上色，可以发现，如果位置 (i, j) 的元素为 1，那么它可以作为一个边长为 4 的正方形的右下角，f 值至少为 4，即：

f[i][j]≥min(f[i][j−1],f[i−1][j],f[i−1][j−1])+1

将其与上一个不等式联立，可以得到：

f[i][j]=min(f[i][j−1],f[i−1][j],f[i−1][j−1])+1

这样我们就得到了 f\[i\]\[j\] 的递推式。此外还要考虑边界（i = 0 或 j = 0）以及位置 (i, j) 的元素为 0 的情况，可以得到如下完整的递推式：

![在这里插入图片描述][20200508231426829.png]

我们按照行优先的顺序依次计算 f\[i\]\[j\] 的值，就可以得到最终的答案。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bmZlbmdmZW5nZmVuZw_size_16_color_FFFFFF_t_70]: /images/20230312/c8630a27a6544a9989d9087bfbd8093e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bmZlbmdmZW5nZmVuZw_size_16_color_FFFFFF_t_70 1]: /images/20230312/e8a23c61fcd34fc3a7b4b7dac428e240.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bmZlbmdmZW5nZmVuZw_size_16_color_FFFFFF_t_70 2]: /images/20230312/abb862a2b7b44e69a2db53c1a9438ceb.png
[20200508231426829.png]: /images/20230312/644acece98f544cea26a04311c0d8acf.png