leetcode221 最大正方形

题目

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

示例:

输入:

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

输出: 4

分析

动态规划问题。本题完全没看其他题解自己想出来的状态转移方程，还是很有成就感的。设dp[i][j]表示到（i,j）位置时，可形成的最大的矩形边长。它的值为它相邻的上、左、和左上三个位置的可形成最大矩形边长加一。
边界条件：略。
状态转移方程：dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1。

代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {

        if (matrix.empty()){
            return 0;
        }

        int row = matrix.size();
        int col = matrix[0].size();
        int res = 0;

        vector<vector<int>> dp(row, vector<int>(col, 0));

        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (i == 0 || j == 0){
                    dp[i][j] = matrix[i][j] - '0';
                }else if(matrix[i][j] != '0'){
                    int min_s = INT_MAX;
                    min_s = min(min_s, dp[i - 1][j]);
                    min_s = min(min_s, dp[i][j - 1]);
                    min_s = min(min_s, dp[i - 1][j - 1]);
                    dp[i][j] = min_s + 1;
                }
                
                res = max(res, dp[i][j]);
            }
        }

        return res * res;
    }
};