Leetcode 221. 最大正方形

心路历程这道题是一个动态规划题但是其实递推关系很难想到如下图所示MDP建模状态以i,j为右下角的正方形动作候选集这道题的动作候选集其实是是否选择其左上角邻接的三个位置动作候选集的特征不是特别明显。返回值最大正方形的边长注意的点1、注意题目中给出的是’0’而不是02、注意边长要转化为面积解法动态规划DP数组classSolution:defmaximalSquare(self,matrix:List[List[str]])-int:iflen(matrix)0orlen(matrix[0])0:return0n,mlen(matrix),len(matrix[0])dp[[0]*mfor_inrange(n)]# 注意初始化不要用*maxl0foriinrange(n):forjinrange(m):ifmatrix[i][j]1:ifi!0andj!0:# 边界条件等于特殊情况dp[i][j]min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])1else:dp[i][j]1maxlmax(maxl,dp[i][j])returnmaxl*maxl递归classSolution:defmaximalSquare(self,matrix:List[List[str]])-int:n,mlen(matrix),len(matrix[0])cachedefdp(i,j):# 以i,j为右下顶点的正方形的边长最大值ifmatrix[i][j]0:return0ifnot(0in)ornot(0jm):return0returnmin(dp(i-1,j-1),dp(i,j-1),dp(i-1,j))1res0foriinrange(n):forjinrange(m):resmax(res,dp(i,j))returnres**2