关于leetcode:leetcode221-最大正方形-动态规划法

在一个由 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)dp(i, j)dp(i,j) 示意以 (i,j)(i, j)(i,j) 为右下角，且只蕴含 111 的正方形的边长最大值。如果咱们能计算出所有 dp(i,j)dp(i, j)dp(i,j) 的值，那么其中的最大值即为矩阵中只蕴含 111 的正方形的边长最大值，其平方即为最大正方形的面积。

如果该地位的值是 000，则 dp(i,j)=0dp(i, j) = 0dp(i,j)=0，因为以后地位不可能在由 111 组成的正方形中；

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

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

js 解法：

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {if (!matrix.length || !matrix[0].length) return 0
    var maxSlideLen = 0, // 记录最长边
        dp = Array(matrix.length); // 构建 dp 数组

    for (var i = 0; i < matrix.length; i++) {dp[i] = Array(matrix[0].length).fill(0); // 填充每一位为 0
        for (let j = 0; j < matrix[0].length; j++) {if (matrix[i][j] === 1) {if (i === 0 || j === 0) {dp[i][j] = 1; // 第一列和第一行的 dp 值为 1
                } else {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 // 判断左上，左下，右上是否有 0
                }
                maxSlideLen = Math.max(maxSlideLen, dp[i][j]) // 更新最大边长
            }
        }
    }
    return maxSlideLen ** 2 // 求最大边长面积
};