今天和大家聊的问题叫做 最大正方形，我们先来看题面：https://leetcode-cn.com/problems/maximal-square/
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
解题
动态规划
设矩阵的长宽为m,n，dp[m+1][n+1],
其中dp[i][j]表示以(i-1,j-1)为右下方元素的最大正方形的边长，初始dp全为0
遍历矩阵中每一个元素，若matrix(i,j)=0,则跳过
若matrix(i,j)不为0，则dp[i][j]的值由dp[i-1][j-1] dp[i-1][j] dp[i][j-1]的最小值决定
有两种情况：
1) dp[i-1][j-1] dp[i-1][j] dp[i][j-1]中至少有一个值为0，说明矩阵中对应位置为0，则以(i,j)为右下方的正方形边长为1
2）dp[i-1][j-1] dp[i-1][j] dp[i][j-1]的值都不为0，则dp[i][j]的值为dp[i-1][j-1] dp[i-1][j] dp[i][j-1]的最小值+1
class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { //dp[i][j]表示以(i,j)为右下角能构成的最大正方形边长 int m=matrix.size(); if(m<1) return 0; int n=matrix[0].size(); vector<vector<int>> dp(m+1,vector<int>(n+1,0)); int imax=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { if(matrix[i-1][j-1]=='1') dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1; imax=max(imax,dp[i][j]); } return imax*imax; } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
