问题描述
在一个二维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;
}
}
