Maximal Square

题目来源
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.
寻找最大矩形。想到应该用DP，但是还没想到应该怎么用。
突然想到之前做过找最大长方形的，也可以用类似的方法。想想不行。
然后想想利用dp[i][j]和dp[i-1][j-1]的关系也是可行的。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0)
            return 0;
        int n = matrix[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i=1; i<=m; i++)
            for (int j=1; j<=n; j++) {
                if (matrix[i-1][j-1] == '0')
                    dp[i][j] = 0;
                else {
                    dp[i][j]++;
                    for (int k=1; k<=dp[i-1][j-1]; k++) {
                        if (matrix[i-k-1][j-1] != '1' || matrix[i-1][j-k-1] != '1')
                            break;
                        dp[i][j]++;
                    }
                }
            }
        int res = 0;
        for (int i=1; i<=m; i++)
            for (int j=1; j<=n; j++)
                res = max(res, dp[i][j] * dp[i][j]);
        return res;
    }
};

看了看讨论区，发现可以改进，直接如下：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0)
            return 0;
        int n = matrix[0].size();
        int res = 0;
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i=1; i<=m; i++)
            for (int j=1; j<=n; j++) {
                if (matrix[i-1][j-1] == '0')
                    dp[i][j] = 0;
                else {
                    dp[i][j] = min(dp[i-1][j-1] + 1, min(dp[i-1][j], dp[i][j-1]) + 1);
                    res = max(res, dp[i][j] * dp[i][j]);
                }
            }
        return res;
    }
};