乌审旗建设局网站四川省工程造价总站官网

221. 最大正方形

看到这个题目真能立马想到dp吗？貌似很难，即使知道是一个dp题也很难想到解法。

直观来看，使用bfs以一个点为中点进行遍历，需要的时间复杂度为$O(n^2{m}^2)$

但是可以很容易发现，如果求以一个点为角 构成的最大正方形，可以通过其他周围的点作为角来快速找到这个点的最大正方形。

我们用数组存以该点为右下角，左下角，左上角，右上角的最大正方形，可以通过周围的转移，然后求出以它为“中心”构成的最大正方形。于是有如下代码

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();if(n == 1 && m == 1) return matrix[0][0];vector<vector<vector<int>>> dp(n, vector<int>(m, vector<int>(4, 0)));int ans = 0;for(int j = 0; j < m; ++ j){dp[0][j][0] = dp[0][j][1]= dp[0][j][2] = dp[0][j][3] = matrix[0][j];}for(int i = 1; i < n - 1; ++ i){dp[i][0][0] = dp[i][0][1] = dp[i][0][2] = dp[i][0][3] = matrix[i][0];for(int j = 1; j < m - 1; ++ j){dp[i][j][0] = min(dp[i - 1][j][0], min(dp[i - 1][j - 1][0], dp[i][j - 1][0])) + 1;dp[i][j][1] = min(dp[i - 1][j][1], min(dp[i - 1][j + 1][1], dp[i][j + 1][1])) + 1;····}//最后一列}//最后一行return ans * ans;}
};

但是实际上，以该点为右下角就足以解决这个问题，因为对于任何一个最大正方形而言，它一定有一个右下角，那么找到这个右下角能构成的最大正方形就是这个正方形了。

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