题解 | #最大正方形#

import java.util.*;
//采用动态规划，该问题明显具有最优子结构。
//递推关系式：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] = 0，dp[i][j]=0;
public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
        // write code here
        int len1 = matrix.length;//二维数组的一维长度
        //特殊值（空数组）处理
        if(len1 == 0){
            return 0;
        }
        
        int len2 = matrix[0].length;//二维数组的二维长度
        //特殊值（空数组）处理
        if(len2 == 0){
            return 0;
        }
        //特殊值（最大正方形面积为1）处理
        if(len1==1 || len2==1){
            for(int i=0;i<len1;i++){
                for(int j=0;j<len2;j++){
                    if(matrix[i][j] == '1'){
                        return 1;
                    }
                }
            }
        }
        int[][] dp = new int[len1][len2];//二维dp数组，其中dp[i][j]表示的是在矩阵中以坐标(i,j)为右下角的最大正方形边长
        //初始化第一列
        for(int i=0;i<len1;i++){
            if(matrix[i][0] == '1'){
                dp[i][0] = 1;
            }else{
                dp[i][0] = 0;
            }
        }
        //初始化第一行
        for(int i=0;i<len2;i++){
            if(matrix[0][i] == '1'){
                dp[0][i] = 1;
            }else{
                dp[0][i] = 0;
            }
        }
        int max = 1;//最大正方形的边长
        //从第二行，第二列开始遍历
        for(int i=1;i<len1;i++){
            for(int j=1;j<len2;j++){
                if(matrix[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] = 0，dp[i][j]=0;
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    if(dp[i][j] > max){
                        max = dp[i][j];
                    }
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        
        return max*max;
    }
}