15 动态规划解统计全为1的正方形子矩阵

本文介绍: 分析：可以使用动态规划求解 dp[i][j]表示以[i][j]为底的最大正方形，如果matrix[i][j]=1则d p[i][j]=min(d p[i-1][j],d p[i-1][j-1],d p[i][j-1])+1,否则为0。描述，给你一个 m*n的矩阵，矩阵中的元素不是0就是1，请你统计并返回其中完全由1组成的正方形子矩形的个数；来源：Lee tCo de第1277题。

来源：Lee tCo de第1277题

难度：中等

描述，给你一个 m*n的矩阵，矩阵中的元素不是0就是1，请你统计并返回其中完全由1组成的正方形子矩形的个数；

分析：可以使用动态规划求解 d p[i][j]表示以[i][j]为底的最大正方形，如果matrix[i][j]=1则d p[i][j]=m in(d p[i-1][j],d p[i-1][j-1],d p[i][j-1])+1,否则为0。

public int maxSquare(int [][]matrix)
{
//申请动态数组
int [][]dp=new int[matrix.length][matrix[0].length];
//动态数组第一列初始化
for(int i=0;i&lt;matrix.length;i++)
{
if(matrix[i][0]==1)
{
dp[i][0]=1;
}else
{
dp[i][0]=0;
}
}
//动态数组不第一行初始化
for(int i=0;i<matrix[0].length;i++)
{
if(matrix[0][i]==1)
{
dp[0][i]=1;
}else
{
dp[0][i]=0;
}
}
//动态数组求值
for(int i=1;i<matrix.length;i++)
{
for(int j=1;j<matrix[i].length;j++)
{
if(matrix[i][j]==1)
{
dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}else
{
dp[i][j]=0;
}
}
}
int max=Interger.MIN_VALUE;
//求取最大值
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix[i].length;j++)
{
max=Math.max(max,dp[i][j]);
}
}
return max;
}