221. Maximal Square(动态规划)

发布时间：2020-12-14 04:23:09 所属栏目：大数据来源：网络整理

导读：Given a 2D binary matrix filled with 0‘s and 1‘s,find the largest square containing only 1‘s and return its area. Example: Input: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0Output: 4 dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1 ;

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

dp[i][j] =  min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;

 1 class Solution {
 2 public:
 3     int maximalSquare(vector<vector<char>>& matrix) {
 4         int n = matrix.size();
 5         if(n==0) return 0;
 6         int m = matrix[0].size();
 7         vector<vector<int> > dp(n+1,vector<int>(m+1,0));
 8         int res =0;
 9         for(int i = 1;i <=n;i++)
10             for(int j = 1;j<=m;j++){
11 
12                 if(matrix[i-1][j-1]==‘1‘)
13                     dp[i][j] =  min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
14                     res  = max(res,dp[i][j]);
15                 }
16          
17         return res*res;
18     }
19     
20 };

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!