动态规划解最大正方形面积（多解）

LeetCode221在一个由0和1组成的二维矩阵内找到只包含1的最大正方形并返回其面积。示例输入matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]输出4Python解法1.暴力法class Solution: def maximalSquare(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 m len(matrix) n len(matrix[0]) max_side 0 for i in range(m): for j in range(n): if matrix[i][j] 1: count_side 1 # 能拓展的最大边界 while i count_side m and j count_side n: flag True # 检查新增的一行右侧列 for k in range(i, i count_side 1): if matrix[k][j count_side] 0: flag False break if not flag: break # 检查新增的一列底行 for k in range(j, j count_side 1): if matrix[i count_side][k] 0: flag False break if flag: count_side 1 else: break max_side max(max_side, count_side) return max_side * max_side遍历矩阵中的每个元素遇到 1则将该元素作为正方形的左上角确定正方形的左上角后根据左上角所在的行和列计算可能的最大正方形的边长在该边长范围内寻找只包含 1 的最大正方形每次在下方新增一行以及在右方新增一列判断新增的行和列是否满足所有元素都是 1。2.动态规划class Solution: def maximalSquare(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 m len(matrix) n len(matrix[0]) max_side 0 #创建二维表 dp [[0] * n for _ in range(m)] for i in range(m): for j in range(n): if matrix[i][j] 1: if i 0 and j 0: dp[i][j] 1 else: #dp[i][j]代表以坐标点(i,j) 为右下角的最大正方形 dp[i][j] min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) 1 max_side max(max_side, dp[i][j]) return max_side * max_side一、整体思路题目目标是找出矩阵中全部由 1 构成的正方形返回正方形面积。动态规划核心思路是定义一个 dp 二维数组数组每个位置的值代表以当前坐标格子作为正方形右下角时能形成的最大正方形边长遍历整个矩阵不断更新最长边长最后边长平方就是最大面积。二、前置边界判断首先处理空矩阵特殊情况如果矩阵本身为空或者矩阵存在但第一行没有元素说明不存在任何正方形直接返回 0。三、变量与 dp 数组定义m 代表矩阵总行数n 代表矩阵总列数max_side 用来记录遍历过程中出现过的最大正方形边长初始值设为 0。 dp 数组和原矩阵行列大小完全一致所有元素初始化为 0dp [i][j] 的含义以原矩阵第 i 行第 j 列格子为右下角仅由 1 组成的正方形的最大边长。四、双层循环遍历矩阵逐行逐列扫描矩阵每一个格子分两种情况处理格子内容为 0 和 1 的场景。如果当前格子内容是字符 0当前位置无法作为有效正方形右下角对应 dp 数组该位置保持初始 0不参与边长更新。如果当前格子内容是字符 1再细分边界行 / 列与中间区域Java解法动态规划class Solution { public int maximalSquare(char[][] matrix) { if(matrix null || matrix[0] null){ return 0; } int m matrix.length; int n matrix[0].length; int max_side 0; int[][] dp new int[m][n]; for(int i 0; i m; i){ for(int j 0; j n; j){ if(matrix[i][j] 1){ if(i 0 || j 0){ dp[i][j] 1; }else{ dp[i][j] Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) 1; } max_side Math.max(max_side, dp[i][j]); } } } return max_side * max_side; } }注意Java比较不能直接三个比较C解法动态规划class Solution { public: int maximalSquare(vectorvectorchar matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m matrix.size(); int n matrix[0].size(); int maxSide 0; vectorvectorint dp(m, vectorint(n, 0)); for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 1) { if (i 0 || j 0) { dp[i][j] 1; } else { dp[i][j] min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) 1; } maxSide max(maxSide, dp[i][j]); } } } return maxSide * maxSide; } };