题目链接
题目描述
实现代码
动态规划思想:记dp[i][j]表示以位置(i,j)为右下角的最大的正方形的边长,考虑两种情况:
- matrix[i][j] == 0:此时不可能存在该正方形,因此dp[i][j] = 0
- matrix[i][j] == 1:此时的值与其相邻的三个前位置的值相关,状态转移方程为:
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
实现代码:
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int max = 0;
for(int i=0; i<m; i++) {
dp[i][0] = matrix[i][0] - '0';
max =( max >= dp[i][0] ? max : 1);
}
for(int j=0; j<n; j++) {
dp[0][j] = matrix[0][j] - '0';
max = ( max >= dp[0][j] ? max : 1);
}
for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {
if(matrix[i][j] == '0') {
continue;
}
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1;
max = ( max >= dp[i][j] ? max : dp[i][j]);
}
}
return max * max;
}
}