动态规划：01矩阵中全为1的最大正方形边长

问题描述

在一个二维0 1矩阵中找到全为1的最大正方形，返回其边长。

输入：

1 0 1 0 0 
1 0 1 1 1 
1 1 1 1 1 
1 0 0 1 0

输出：

2

思路：

动态规划，构造一个等大小的dp[n][m]矩阵，dp[i][j]表示以matrix[i][j]为右下角的全1正方形的边长。初始化dp[i][0]和dp[0][j]分别为matrix[i][0]和matrix[0][j]，因为以边缘这一行一列中的点为右下角的全1正方形边长只有0和1两种情况，分别由他们本身是0还是1决定。初始化之后开始遍历这个dp矩阵，如果matrix[i][j]为0，则dp[i][j]为1，如果matrix[i][j]为1，则dp[i][j]=min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]}+1，这一步可以这样理解：

矩阵示意图
只有满足matrix[i][j]左方上方和左上方三个地方的正方形边长为2的时候，它的边长才能为3，任意一个为1，则它的边长为2，所以取三者最小值+1就是以该点为右下角的全1正方形边长。最后只用遍历dp矩阵找出最大值即可。

代码：

public class Solution {
    public int FindAllOneSquare(int [][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++){
            dp[i][0] = matrix[i][0];
        }
        for (int j = 0; j < n;j++){
            dp[0][j] = matrix[0][j];
        }
        for (int i=1; i < m; i++){
            for (int j = 1; j < n; j++){
                if (matrix[i][j] == 0)
                    dp[i][j] = 0;
                else {
                    dp[i][j] = Math.min(dp[i-1][j-1],
                            Math.min(dp[i][j-1], dp[i-1][j])) + 1;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (dp[i][j] > max)
                    max = dp[i][j];
            }
        }
        return max;
    }
}