[LeetCode]Maximal Square

我们用DP[i][j][k]来表示以matrix[i][j]为左上顶点的长度为k的区域是否是square，我们可以得到递推公式：

• DP[i][j][k] = true, if DP[i][j][k - 1], DP[i - 1][j][k - 1], DP[i][j - 1][k - 1], DP[i - 1][j - 1][k - 1]均为true
• 否则，DP[i][j][k] = false

假设输入matrix为m * n，时间复杂度O(m * n * min(m , n))，空间复杂度O(m * n * min(m , n))，代码如下：

	class Solution {
	public:
	int maximalSquare(vector<vector<char>>& matrix) {
	int m = matrix.size(), n = m? matrix[0].size(): 0, k = min(m, n), res = 0;
	if(!m || !n)return 0;
	vector<vector<bool>> dp(m * n, vector<bool>(k + 1, false));
	for(int i = 0; i < m * n; ++i)
	{
	dp[i][1] = matrix[i / n][i % n] == '1';
	if(dp[i][1])res = max(res, 1);
	}
	for(int i = 2; i <= k; ++i)
	{
	for(int a = 0; a <= m - i; ++a)
	{
	for(int b = 0; b <= n - i; ++b)
	{
	int idx = a * n + b;
	dp[idx][i] = dp[idx][i - 1] && dp[idx + 1][i - 1] && dp[idx + n][i - 1] && dp[idx + 1 + n][i - 1];
	if(dp[idx][i])res = max(res, i);
	}
	}
	}
	return res * res;
	}
	};

view raw Maximal Square_3.cpp hosted with ❤ by GitHub

但是很明显这个DP方程效率并不高，如果改变用DP[i][j] = k代表以matrix[i][j]作为右下顶点的square的最大长度为k，我们可以得到效率更高的DP方程，递推公式如下：

• if matrix[i][j] == '1' && DP[i - 1][j] > 0 && DP[i - 1][j - 1] > 0 && DP[i ][j - 1] > 0, DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i ][j - 1] )
• else if matrix[i][j] == '1', DP[i][j] = 1
• else DP[i][j] = 0

这个地推公式画个图很好理解，就不分析了。时间复杂度O(n * m)，空间复杂度O(m * n)，代码如下：

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

view raw Maximal Square_1.cpp hosted with ❤ by GitHub

空间可以优化到O(n)，代码如下：

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

view raw Maximal Square_2.cpp hosted with ❤ by GitHub