content: package question1277_count_square_submatrices_with_all_ones;
  
  /**
   * 动态规划。
   *
   * 状态定义：
   * dp[i][j]表示以matrix[i][j]为右下角的最大正方形边长。
   *
   * 初始化条件：
   * （1）当i == 0时，dp[0][j] = matrix[0][j]
   * （2）当j == 0时，dp[i][0] = matrix[i][0]
   *
   * 状态转移方程：
   * （1）当matrix[i][j] == 1时，dp[i][j] = min(dp[i - 1][j - 1], max1, max2)，
   * 其中 max1 为第 j 列中从 i - 1 行往前的连续的 1 的个数， max2 为第 i 行中从 j - 1 列往前的连续的 1 的个数。
   * （2）当matrix[i][j] == 0时，dp[i][j] = 0。
   *
   * 时间复杂度和空间复杂度均是O(m * n)，其中m为矩阵matrix的行数，n为矩阵matrix的列数。
   *
   * 执行用时：5ms，击败94.15%。消耗内存：42.7MB，击败62.50%。
   */
  public class Solution {
      public int countSquares(int[][] matrix) {
          int m;
          if (null == matrix || (m = matrix.length) == 0) {
              return 0;
          }
          int n;
          if (null == matrix[0] || (n = matrix[0].length) == 0) {
              return 0;
          }
          int[][] dp = new int[m][n];
          int result = 0;
          for (int i = 0; i < n; i++) {
              if (matrix[0][i] == 1) {
                  dp[0][i] = 1;
                  result++;
              }
          }
          for (int i = 1; i < m; i++) {
              if (matrix[i][0] == 1) {
                  dp[i][0] = 1;
                  result++;
              }
          }
          for (int i = 1; i < m; i++) {
              for (int j = 1; j < n; j++) {
                  if (matrix[i][j] == 1) {
                      int max1 = 0, max2 = 0;
                      for (int k = i - 1; k >= 0 && matrix[k][j] == 1; k--) {
                          max1++;
                      }
                      for (int k = j - 1; k >= 0 && matrix[i][k] == 1; k--) {
                          max2++;
                      }
                      dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(max1, max2)) + 1;
                      result += dp[i][j];
                  }
              }
          }
          return result;
      }
  }