题目描述：
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 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
解题思路： 动态规划
1. 用size[i][j] 表示从（0，0）到（i，j)的最大正方形边长
2.考虑动态转移方程：
情况1: matrix[i][j]=0
此时size[i][j]与size[i-1][j-1]不会增大，最大正方形的情形已经在size[i-1][j-1]处考虑过了，可以忽略不计。
情况2: matrix[i][j]=1
image.png
有上述四种情况可得：
size[i][j] = min(size[i-1][j-1], size[i-1][j], size[i][j-1])+1;
由此，我们得到O(n^2)解法如下:
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size();
int n = matrix[0].size();
//size[i][j]: the largest square size from (0,0) to (i,j)
vector<vector<int>> size(m,vector<int>(n,0));
int res = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j< n;j++){
size[i][j] = matrix[i][j]-'0';
if(!size[i][j]) continue;
if(i == 0 || j==0){
//size[0][0] = 0, do nothing here
}else if(i == 0)
size[i][j] = size[i][j-1]+1;
else if(j == 0)
size[i][j] = size[i-1][j]+1;
else
size[i][j] = min(min(size[i-1][j-1],
size[i-1][j]),
size[i][j-1])+1;
res = max(res,size[i][j]*size[i][j]);
}
return res;
}
};
