題目描述：

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

解題思路： 動(dòng)態(tài)規(guī)劃

1. 用size[i][j] 表示從（0，0）到（i，j)的最大正方形邊長(zhǎng)

2.考慮動(dòng)態(tài)轉(zhuǎn)移方程：

情況1: matrix[i][j]=0
此時(shí)size[i][j]與size[i-1][j-1]不會(huì)增大，最大正方形的情形已經(jīng)在size[i-1][j-1]處考慮過(guò)了，可以忽略不計(jì)。

情況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;
    }
};