题目
在一个由 ‘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
解题
方法一：动态规划
就像 木桶的短板理论 那样——附近的最小边长，才与 ? 的最长边长有关。
class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { int m=matrix.size(),n=matrix[0].size(); vector<vector<int>> dp(m+1,vector<int>(n+1)); int maxLen=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(matrix[i][j]=='1'){ dp[i+1][j+1]=min({dp[i][j],dp[i+1][j],dp[i][j+1]})+1; maxLen=max(maxLen,dp[i+1][j+1]); } } } return maxLen*maxLen; } };
