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

  DP, dp[i][j]表示右下角落在(i, j)的最大正方形的边长。 遍历grid，如果当前点为1，那它可能为这些情况作出贡献： 1. 拓展左面的最大正方形，那它往上也要有足够的1； 2. 拓展上面的最大正方形，那它往左也要有足够的1； 3. 拓展左上的最大正方形，那它往上往左都要有足够的1. 最后取得是这三种情况的最小值+1， 也就是找到这个构成边长“足够的1”+1， 画图很好理解   这里要dp的同时更新这个最大边长，最后返还的是面积 时间空间复杂度都是O(mn)，优化也是只用当前行和前一行使得space到O(n)   实现：

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