https://leetcode-cn.com/problems/maximal-square/submissions/

    • dp[ i ][ j ]:
      • 表示以 (i, j)(i,j) 为右下角，且只包含 1的正方形的边长最大值

    先来阐述简单共识

    • 若形成正方形（非单 1），以当前为右下角的视角看，则需要：当前格、上、左、左上都是 1
    • 可以换个角度：当前格、上、左、左上都不能受 0 的限制，才能成为正方形

    image.png
    上面详解了 三者取最小 的含义：

    • 图 1：受限于左上的 0
    • 图 2：受限于上边的 0
    • 图 3：受限于左边的 0
    • 数字表示：以此为正方形右下角的最大边长
    • 黄色表示：格子 ? 作为右下角的正方形区域

    就像 木桶的短板理论 那样——附近的最小边长，才与 ? 的最长边长有关。

    1.  public int maximalSquare(char[][] matrix) {
    2.      int N = matrix.length;
    3.      int M = matrix[0].length;
    4.      int[][] dp = new int[N][M];
    5.      int max = 0;
    6.      for (int j = 0; j < M; j++) {
    7.          if (matrix[0][j] == '1') {
    8.              dp[0][j] = 1;
    9.              max = 1;
    10.          }
    11.      }
    12.      for (int i = 0; i < N; i++) {
    13.          if (matrix[i][0] == '1') {
    14.              dp[i][0] = 1;
    15.              max = 1;
    16.          }
    17.      }
    18.      for (int i = 1; i < N; i++) {
    19.          for (int j = 1; j < M; j++) {
    20.              if (matrix[i][j] != '1') {
    21.                  continue;
    22.              }
    23.              dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
    24.              max = Math.max(max, dp[i][j]);
    25.          }
    26.      }
    27.      return max * max;
    28.  }