[数据结构与算法]Leetcode笔记----NC108.最大正方形

描述
给定一个由’0’和’1’组成的2维矩阵，返回该矩阵中最大的由’1’组成的正方形的面积

本题的思路是动态规划，因为数组中每个位置的面积依赖于其相邻位置的状态，那么难点其实在于动态规划数组中元素代表的含义。本题中元素的含义应为“以该位置为右下角的正方形的边长”，数组中具体每个元素的赋值规则如下：如果该元素在最上/最左或该元素为0，那么dp[i][j]就是他本身的值，如果该元素在数组中间且本身为1，则判断它左上、左边、上方三个位置的dp元素，若均不是0则其值为三个位置dp元素最小值+1，只要有一个是0则说明围不成正方形，dp[i][j]=0

public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
        // write code here
        int dp [][] = new int [matrix.length][matrix[0].length];
        int res = 0;
        for(int i = 0;i < matrix.length;i++){
            for(int j = 0;j < matrix[0].length;j++){
                if(matrix[i][j] == '0'||i==0||j==0){
                    dp[i][j] = matrix[i][j]-'0';
                }
                else {
                    if(matrix[i-1][j-1]!='0'&&matrix[i][j-1]!='0'&&matrix[i-1][j]!='0'){
                        int min = Math.min(dp[i-1][j-1],dp[i-1][j]);
                        dp[i][j] = Math.min(min,dp[i][j-1])+1;
                    }
                    else{
                        dp[i][j] = 1;
                    }
                    if(dp[i][j]*dp[i][j] > res){
                            res = dp[i][j]*dp[i][j];
                        }
                }
            }
        }
        return res;
    }
}