LeetCode题解：221. 最大正方形，动态规划，JavaScript，详细注释

[chencl1986]

原题链接：221. 最大正方形

解题思路：

1. 假设matrix[i][j] === ’1‘，它自己是一个正方形。
2. 只有在matrix[i - 1][j]、matrix[i][j - 1]、matrix[i - 1][j - 1]都为'1'的时候，才能形成一个更大的正方形。
3. 如果用dp数组递推，dp[i][j]代表当前的最大正方形边长，它是由dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1]的状态递推而来。
4. 因此dp是一个(m+1)*(n+1)的矩阵。
5. matrix[i - 1][j - 1] === '1'时，dp[i][j]才可以与之前已知的边长组成新的正方形。由于是正方形，因此只能取之前状态的最小值，否则就成了长方形。
6. 状态转移方程为：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1。当前位置的边长需要记为1。
7. 每次递推后，都要记录当前得到的边长最大值max，最终返回max ** 2，即为最大面积。

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  const m = matrix.length; // 缓存矩阵行数
  const n = matrix[0].length; // 缓存矩阵列数
  // 创建一个m+1行n+1列的矩阵用于递推
  // 由于递推matrix的时候的第一行和第一列，需要判断-1行和-1列的最小值
  // 因此初始化dp的第一行和第一列都为0，dp的i行和j列对应的是matrix的i-1行i-1列
  // 创建dp时只要存入第一行的值
  let dp = [new Array(n + 1).fill(0)];
  let max = 0; // 存储遇到的最大正方形边长

  // 递推matrix的每个位置，计算每个位置能形成的正方形最大边长
  for (let i = 1; i <= m; i++) {
    // 每次循环dp中存入当前行的值
    dp.push(new Array(n + 1).fill(0));

    for (let j = 1; j <= n; j++) {
      // 当遇到矩阵值为1时，表示当前存在正方形
      if (matrix[i - 1][j - 1] === '1') {
        // 计算当前位置能形成的最大正方形边长
        dp[i][j] =
          // 当前位置是和左、上、左上3个方向形成正方形
          // 能形成的最大正方形会受到这3个位置的限制，因此取最小值
          Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) +
          // 当前位置的自身的边长
          1;
        // 记录所有边长的最大值
        max = Math.max(max, dp[i][j]);
      }
    }
  }

  // 最大边长的平方是最大面积
  return max ** 2;
};