221. Maximal Square

Let dp[i][j] be the maximal size of square that can be reached at matrix[i][j]. Let's have a look at some examples to get a sense of how to achieve the state equation:

matrix1 = [ [1, 1, 0], [1, 1, 1], [1, 1, 1] ]
matrix2 = [ [1, 1, 1], [1, 1, 1], [1, 0, 1] ]
matrix3 = [ [0, 1, 1], [1, 1, 1], [1, 1, 1]]

You'll see that dp[2][2] in all of these three matrixes is 2. For matrix1, it is the dp[1][2] who is 1 that restricts dp[2][2]. For matrix2, it is the dp[2][1] and while for matrix3, it is the dp[1][1]. Therefore, for dp[i][j], we have dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

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