今天继续攻克Dynamic Programming。接下来要分析的一道题是maximal square。
题目是说给我们一个只包含0和1的二维矩阵，让我们找出最大的只包含1的最大的正方形，返回这个正方形的面积。
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
通过前面做DP题目的经验，我发现如果能直接从下到上地分析，其实并不一定从从上到下地开始分析，因为那太费时间。我发现这就是一题可以从下到上直接分析的题目。
对于这样一个矩阵，我们可以新建一个同样维度的矩阵dp，就表示以i，j作为我们要找的正方形的右下角的点，那么这个正方形的边长是多少。
我们不难总结出这样的公式：
当， 那么
。因为此处值为0，无法组成值均为1的正方形；
当，有
，这是因为左上角，左边，上面这三个值的最小值表示的是这三个正方形的重合部分，+1则能够表示以i，j为右下角的正方形的边长。
有了这个思想，不难写出如下代码
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int row = matrix.length, col = matrix[0].length;
int[][] m = new int[row][col];
int res = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 || j == 0) {
m[i][j] = Character.getNumericValue(matrix[i][j]);
res = Math.max(m[i][j],res);
} else if (Character.getNumericValue(matrix[i][j]) == 1) {
m[i][j] = Math.min(Math.min(m[i-1][j], m[i][j-1]),
m[i-1][j-1]) + 1;
res = Math.max(m[i][j],res);
}
}
}
return res*res;
}
}
但通过查看solution，发现用同一个思想，有更加精简的答案：
public class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
int[][] dp = new int[rows + 1][cols + 1];
int maxsqlen = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (matrix[i-1][j-1] == '1'){
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
maxsqlen = Math.max(maxsqlen, dp[i][j]);
}
}
}
return maxsqlen * maxsqlen;
}
}
solution中较为精简的答案相对于我的代码一个大的变化是dp矩阵的维度改变int[][] dp = new int[rows + 1][cols + 1];
这个改变使得在for loop中不需要先确认是否是第1行或者第一列。别的基本是一致的。但这个改变还是在一定程度上加快了运算。
当答案到这里，已经是一个经典的dp解法了，但solution中还给出了另一种更加高效的dp解法。
我们注意到更新过程用的公式是。与前面coin change2使用相同的思想，我们可以并不需要储存每一行的数据，而是可以直接更新每一行的数据，也就是把
表示为
dp[i-1][j]
dp[j]$，这里用prev来表示：
class Solution {
public int maximalSquare(char[][] matrix) {
int row = matrix.length, col = (row == 0)? 0: matrix[0].length;
int[] dp = new int[col+1];
int maxsqlen = 0, prev = 0;
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
int tmp = dp[j];
if (matrix[i-1][j-1] == '1') {
dp[j] =Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
maxsqlen = Math.max(maxsqlen, dp[j]);
} else {
dp[j] = 0;
}
prev = tmp;
}
}
return maxsqlen*maxsqlen;
}
}
改进后的方法节约了一些momory。
总结
很多dp问题不一定要先从recursion的思想开始思考，可以直接从下到上地用iteration的方法思考。
