题解 | #最大正方形，dp#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     [1,0,1,0,0],
     [1,0,1,1,1],
     [1,1,1,1,1],
     [1,0,0,1,0]
     */
    public int solve (char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0 ;
        //f[i][j]表示以matrix[i][j]为右下角的正方形的 边长
        int[][] f = new int[matrix.length][matrix[0].length] ;
        int maxLen = 0 ;
        for(int i = 0 ; i < f.length ; i ++) {
            for(int j = 0 ; j < f[0].length ; j ++) {
                if(matrix[i][j] == '0') continue ;
                if(i == 0 || j == 0) {
                    f[i][j] = 1;
                } else {
                    //转移方程，从 (上，左，上左) 这三个位置转移过来 
                    f[i][j] = Math.min(Math.min(f[i-1][j] , f[i][j - 1]) , f[i-1][j-1]) + 1 ;
                }
                if(f[i][j] > maxLen) maxLen = f[i][j] ;
            }
        }
        return maxLen * maxLen ;
    }
}