本题大意：给出一个只包含0和1的2D的二维数组，求出只包含1的正方形的面积大小。例如：
答案应为4。
解题思路：dp算法。假定当前结点为matrix[x][y] ，则将以该点为右下角的正方形的边长记为：f[x][y]。显然，当matrix[x][y] == '0'时，f[x][y] = 0；如果f[x][y] == '1'，找出dp的递推公式：f[x][y] = min(f[x-1][y], f[x][y-1], f[x-1][y-1]) + 1;
1 class Solution { 2 public: 3 int maximalSquare(vector<vector<char>>& matrix) { 4 if(matrix.empty() || matrix[0].empty() ) return 0; 5 int m = matrix.size(); 6 int n = matrix[0].size(); 7 int f[m][n]; 8 int maxS = 0; 9 for(int i = 0; i < m; i++) 10 { 11 if(matrix[i][0] == '1') 12 { 13 f[i][0] = 1; 14 maxS = 1; 15 } 16 else f[i][0] = 0; 17 } 18 for(int j = 0; j < n; j++) 19 { 20 if(matrix[0][j] == '1') 21 { 22 f[0][j] = 1; 23 maxS = 1; 24 } 25 else f[0][j] = 0; 26 } #初始化第一行和第一列 27 for(int i = 1; i < m; i++) 28 { 29 for(int j = 1; j < n; j++) 30 { 31 if(matrix[i][j] == '0') f[i][j] = 0; 32 else 33 { 34 f[i][j] = min( f[i-1][j], min(f[i][j-1], f[i-1][j-1])) + 1; 35 maxS = max(maxS, f[i][j]); 36 } 37 } 38 } 39 return maxS * maxS; 40 } 41 };