【算法题】221. 最大正方形-力扣(LeetCode)
【算法题】221. 最大正方形-力扣(LeetCode)
1.题目
下方是力扣官方题目的地址
221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：
输入：matrix = [["0"]]
输出：0
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]为'0'或'1'
2.题解
思路
这题可以用动态规划来解决
这题的关键在于正确找到dp数组所代表的意义
一般的思路是想到用dp[i] [j]来表示这个区域中的最大正方形的边长。
不过我们仔细一想，这样子很难用动态规划来解决该问题。
所以我们不妨换个思路：
用dp[i] [j]代表以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。然后在dp[i] [j]中找到的最大值就是最大边长。
如果matrix[i] [j]=0的话，那么dp[i] [j] 为0；如果为1的话，那么至少也是1。至于能不能变大，就得向左上角扩伸。能够扩伸的前提是三个方向都需要能够扩伸，所以我们得取三个方向的dp的最小值，再加上一个1。
所以我们就可以得出状态转移方程：
dp[i][j]+=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
得出了转移方程，再考虑一些特殊值，这题 就可以解决了
Python代码
class Solution(object):
def countSquares(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
n=len(matrix)
m=len(matrix[0])
ans=0
dp=[[0]*m for _ in range(n)]
for i in range(n):
for j in range(m):
if matrix[i][j]==1:
if i==0 or j==0:dp[i][j]=1 # 给特殊位置的“1”赋值
else:dp[i][j]+=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 # 正常位置的直接利用状态转移方程
ans+=dp[i][j]
return ans
3.结语
本人资历尚浅，发博客主要是记录与学习，欢迎大佬们批评指教！大家也可以在评论区多多交流，相互学习，共同成长。