Leetcode#221.Maximal Square

Posted on | In |

这是一道较为另类的动态规划。

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:

1
2
3
4
5
6
7
8
Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

思路：
要组成一个正方形，就要找到最长的正方形边长。利用二维动态规划保存以每一个位置为正方形右下角的时候，能够找到的最大正方形边长。
考虑第(i, j)位置：

1
2
dp[i-1][j-1]  dp[i-1][j]
dp[i][j-1]    dp[i][j]

状态转移公式 

1
2
if(matrix[i][j] == 1) dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) +1
else dp[i][j] = 0;

这个题的坑在于，输入的是char而不是int，一定要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int row = matrix.size();
        if(row == 0) return 0;
        int col = matrix[0].size();
        if(col == 0) return 0;
        
        vector<vector<int>> dp(row, vector<int>(col, 0));
        int max_edge = 0;

        for(int i = 0; i<row; i++){
            if(matrix[i][0] == '1') dp[i][0] = 1;
            max_edge = max(max_edge, dp[i][0]);
        }
        
        for(int i = 0; i<col; i++){
            if(matrix[0][i] == '1') dp[0][i] = 1;
            max_edge = max(max_edge, dp[0][i]);
        }
        
        
        for(int i = 1; i<row; i++){
            for(int j = 1; j<col; j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) +1;
                    max_edge = max_edge > dp[i][j]? max_edge:dp[i][j];
                }
            }
        }

        return max_edge * max_edge;
    }
};