题目链接

最大正方形

题目描述

image.png

实现代码

动态规划思想：记dp[i][j]表示以位置(i,j)为右下角的最大的正方形的边长，考虑两种情况：

  1. matrix[i][j] == 0：此时不可能存在该正方形，因此dp[i][j] = 0
  2. matrix[i][j] == 1：此时的值与其相邻的三个前位置的值相关，状态转移方程为：

    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1

实现代码：

  1. class Solution {
  2.     public int maximalSquare(char[][] matrix) {
  3.         int m = matrix.length;
  4.         int n = matrix[0].length;
  6.         int[][] dp = new int[m][n];
  8.         int max = 0;
  10.         for(int i=0; i<m; i++) {
  11.             dp[i][0] = matrix[i][0] - '0';
  12.             max =( max >= dp[i][0] ? max : 1);
  13.         }
  14.         for(int j=0; j<n; j++) {
  15.             dp[0][j] = matrix[0][j] - '0';
  16.             max = ( max >= dp[0][j] ? max : 1);
  17.         }
  19.         for(int i=1; i<m; i++) {
  20.             for(int j=1; j<n; j++) {
  21.                 if(matrix[i][j] == '0') {
  22.                     continue;
  23.                 }
  24.                 dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1;
  25.                 max = ( max >= dp[i][j] ? max : dp[i][j]);
  26.             }
  27.         }
  29.         return max * max;
  30.     }
  31. }