Description:
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:
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
Link:
https://leetcode.com/problems/maximal-square/description/
解题方法：
DP:
假设dp[i][j]是以点[i][j]为右下角的正方形可以有的最大的边长。
那么dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]))。
解释：
当matrix[i][j] = 1时候，说明这个点可以从它左上，上，左三个方向来进一步扩大这三个方向的正方形，其扩大的值 = 这三个方向能形成正方形的边的最小值。
Tips:
Time Complexity：
O(mn)时间
O(mn)空间
完整代码：
int maximalSquare(vector<vector<char>>& matrix) {
int row = matrix.size();
if(!row)
return 0;
int col = matrix[0].size();
if(!col)
return 0;
int result = 0;
vector<vector<int>> dp(row, vector<int>(col, 0));
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
if(i != 0 && j != 0)
dp[i][j] += min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
if(matrix[i][j] == '1')
dp[i][j]++;
else
dp[i][j] = 0;
result = max(result, dp[i][j]);
}
}
return result * result;
}
