今天继续攻克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的方法思考。