## Monday, August 7, 2017

### [Leetcode] Maximal Square, Solution

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
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.

[Thoughts]

DP[i, j] 是the length of max square,这个square的最右下角是 (i,j)，那么

1）从DP[i-1, j]表述的square上加一行
2）从DP[i, j-1]表述的square上加一列
3）从DP[i-1, j-1]表述的square上加一行和一列

[Code]
``````1:    int maximalSquare(vector<vector<char>>& matrix) {
2:      if(matrix.size() == 0) return 0;
3:
4:      int row = matrix.size();
5:      int col = matrix[0].size();
6:      vector<vector<int>> dp(row+1, vector<int>(col+1, 0));
7:
8:      int maxLen = 0;
9:      for(int i =1; i<=row; i++) {
10:        for(int j =1; j<= col; j++) {
11:          if(matrix[i-1][j-1] == '1') {
12:            dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])+1 ;
13:            maxLen = max(maxLen, dp[i][j]);
14:          }
15:        }
16:      }
17:      return maxLen*maxLen;
18:    }
``````