博文中会简要介绍Leetcode P0221题目分析及解题思路。
“Maximal Square”是一道比较经典的动态规划题，要求我们得到由'1'构成的最大的正方形。
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Example:
Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4
这道题动态规划的思路比较巧妙，我们先来观察几个由'1'构成的正方形的特点，
令k是正方形的边长，
若k=1，
显然当前grid[r][c]等于1时即可；
若k=2，
c
1 1
r 1 1
不难发现，需要grid[r][c]的左上，左下，右上和右下四个格子里同时为1；
若k=3，
c
1 1 1
1 1 1
r 1 1 1
对于边长为3的正方形，我们可以发现，需要grid[r][c]左上，左下，右上和右下同时满足存在边长为2的正方形；
若k=4，
c
1 1 1 1
1 1 1 1
1 1 1 1
r 1 1 1 1
对于边长为4的正方形，我们可以发现，需要grid[r][c]左上，左下，右上和右下同时满足存在边长为3的正方形；
...依次递推即可
根据上述的观察，我们不难得到递推表达式，
令dp[r][c]表示以grid[r][c]为右下角的正方形的边长，
r = 0 或 c = 0 时，
dp[r][c] = grid[r][c]
否则，若grid[r][c] = 1时，
dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])+1
对于上述的第二个式子，为什么取左上，左下和右上的最小值呢？回顾前面的观察，我们知道想要使边长为k的正方形成立，必须要求左上，左下和右上同时满足边长为k-1的正方形成立，也就是说对于以grid[r][c]为右下角的正方形来说（此时右下角为'1'），其实际边长取决于这三者中最小正方形的边长，即木桶短板效应，所以我们要使用三者中的最小值。
以下是Java的题解代码实现。
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0)
return 0;
int H = matrix.length, W = matrix[0].length, maxLen = 0;
int[][] dp = new int[H][W];
for (int r=0; r<H; ++r) {
for (int c=0; c<W; ++c) {
if (r == 0 || c == 0) {
dp[r][c] = matrix[r][c]-'0';
}
else {
if (matrix[r][c] != '0')
dp[r][c] = min(dp[r-1][c-1], dp[r][c-1], dp[r-1][c])+1;
}
maxLen = Math.max(maxLen, (dp[r][c] > 0)? dp[r][c]: 0);
}
}
return maxLen*maxLen;
}
private int min(int... nums) {
int minVal = nums[0];
for (int num: nums)
minVal = Math.min(minVal, num);
return minVal;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.size() == 0)
return 0;
int H = matrix.size(), W = matrix[0].size(), side = 0;
vector<vector<int>> dp(H, vector<int>(W, 0));
for (int r=0; r<H; ++r) {
for (int c=0; c<W; ++c) {
if (r == 0 || c == 0) {
dp[r][c] = matrix[r][c]-'0';
}
else {
if (matrix[r][c] != '0')
dp[r][c] = min(dp[r-1][c-1],
min(dp[r][c-1], dp[r-1][c]))+1;
}
side = max(side, (dp[r][c] > 0)? dp[r][c]: 0);
}
}
return side*side;
}
};