在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

Solution

参考：@lzhlyle

• 动态规划

dp(i + 1, j + 1) 是以 matrix(i, j) 为右下角的正方形的最大边长

若某格子值为 1，则以此为右下角的正方形的、最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个，再加上此格。

dp 具体定义：dp[i + 1] [j + 1] 表示 「以第 i 行、第 j 列为右下角的正方形的最大边长」

题目要求面积。根据 「面积 = 边长 x 边长」可知，我们只需求出 最大边长 即可。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if (m < 1 || n < 1) return 0;
        int res = 0;

        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    dp[i+1][j+1] = min({dp[i+1][j], dp[i][j+1], dp[i][j]}) + 1;
                    res = max(dp[i+1][j+1], res);
                }
            }
        }
        return res * res;
    }
};