全为1的正方形子矩阵

LeetCode 221：在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形。

LeetCode 1277：统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

两题思想一致，都可以用动态规划的算法来解决，递推式如下：

\begin{equation} dp[i][j] = \begin{cases} matrix[i][j]&\mbox{if $i == 0$ or $j ==0$}\\ 0&\mbox{if $matrix[i][j] == 0$}\\ min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1&\mbox{if $maxtrix[i][j] == 1$} \end{cases} \end{equation}

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return 0;
}
int n = matrix.length, m = matrix[0].length;
int[][] dp = new int[n][m];

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (i == 0 || j == 0) {
            dp[i][j] = matrix[i][j];
        } else if (matrix[i][j] == 1) {
            dp[i][j] =  Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
        }
        count += dp[i][j];
    }
}

• dp[i][j] 的含义：以 matrix[i][j] 为右下角的所有小正方形数目之和，由于固定了右下角，所以计算一定不会重复。
  • 同时可以知道，dp 中的最大值就是只包含 1 的 最大正方形 的边长【以该单元为右下角，最多能够延展的长度】
  • dp 的和就是由 1 组成的 正方形 子矩阵的个数