在一个由 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 //求最大边长面积 };
class Solution(object): def maximalSquare(self, matrix): """ :type matrix: List[List[str]] :rtype: int """ if len(matrix)==0 or len(matrix[0])==0: return 0 maxSlide=0 rows,cols = len(matrix),len(matrix[0]) dp = [[0]*(cols+1) for i in range(rows+1)] for i in range(1,rows+1): for j in range(1,cols+1): if matrix[i-1][j-1] == '1': dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 ## 判断左上，左下，右上是否有0 maxSlide = max(maxSlide, dp[i][j]) ## 更新最大边长 return maxSlide*maxSlide
