JAVA

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4

示例2：

输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1

解题思路
使用动态规划的思想，即原问题的最优解可以由子问题的最优解推导得到。在本问题中，如下图，以坐标（i,j）为右下角的最大全1正方形可以由其左边（i-1,j），上边(i,j-1)，左上角（i-1,j-1）的最大全1正方形中的最小值决定。

所以根据动态规划的思路，我们将状态（bp[i][j]表示什么），和状态转移方程（什么时候bp[i][j]更新，怎样更新）推出来，然后代码围绕这个写就可以。
状态： 即bp[i][j]表示以坐标（i,j）为右下角的最大全1正方形的边长。
状态转移方程: 循环 i ,循环 j，当matrix[i][j]=1 时，进行状态转移 bp[i][j] = Math.min ( bp[ i-1 ][ j ] , bp[ i ][ j-1 ] , bp[ i-1 ][ j-1 ] ) +1

代码

package Code221.maximalSquare;


public class MaximalSquare {
    public static void main(String[] args) {
        char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        System.out.println("最大全1正方形边长为"+MaximalSquare.maximalSquare(matrix));
    }
    public static int maximalSquare(char[][] matrix) {
        int m = matrix.length , n = matrix[0].length , max = 0;
        int [][] bp = new int[m][n];
        for(int i = 0 ; i < m ; i++){
            for(int j = 0; j < n ;j++){
                if(matrix[i][j] != '0'){
                    if(i == 0 || j == 0){
                        bp[i][j] = 1;
                    }else{
                        bp[i][j] = Math.min(Math.min(bp[i-1][j],bp[i][j-1]),bp[i-1][j-1])+1;
                    }
                    max = Math.max(max , bp[i][j]);
                }else{
                    bp[i][j] = 0;
                }
            }
        }
        return max*max;
    }
}