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

示例1

输入：[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
返回值：4

本体知识点：动态规划

1.初步分析如下

1.确定dp[][]数组的含义

此题的dp[i][j]，代表以坐标为(i,j)的元素为右下角的正方形的边长。

2.状态转移方程

dp[i][j]的值取决于dp[i-1][j],dp[i-1][j-1],dp[i][j-1]的最小值 即左方正方形的边长，左上方正方形的边长，上方正方形的边长三者的最小值。

3.边界

由于状态转移方程中涉及i-1，j-1，所以i和j一定要大于0. 故dp[0][] 和 dp[][0]要首先确定。

    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
		//判断二维数组是否有效  
		if(matrix.length == 0 || matrix[0].length==0)return 0;
		int rows = matrix.length;
		int cols = matrix[0].lenght;
		int max;
		//声明数组
		int[][] dp = new int[rows][cols];
		//确定边界值
		for(int i = 0;i<rows;i++){
			if(matrix[i][0] == '1')dp[i][0] = 1;
		}
		for(int j = 0;j<cols;j++){
			if(matrix[0][j]=='1')dp[0][j] = 1;
		}
		//确定中间值
		for(int i = 1; i < rows;i++){
			for(int j = 1;j<cols;j++){
				if(matrix[i][j]=='1'){
					dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
					if(dp[i][j]>max)max = dp[i][j];
				}
			}
		}
		return max*max;
	}

2. 程序的优化，上面的程序时间复杂度为O(NxM),空间复杂度为O(NxM);

基于原数组构建动态规划，去掉dp数组的依赖

  
	/**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
		//判断二维数组是否有效  
		if(matrix.length == 0 || matrix[0].length==0)return 0;
		int rows = matrix.length;
		int cols = matrix[0].lenght;
		//这里与上面解题过程有所区别
		char max;
		for(int i = 1;i<rows;i++){
			for(int j = 1;j<cols;j++){
				if(matrix[i][j] == '1'){
					matrix = (char)Math.min(Math.min(matrix[i-1][j-1],matrix[i-1][j]),matrix[i][j-1])+1;
					if(matrix[i][j]>max)max = matrix[i][j];
				}
			}
		}
		return (max-'0')*(max-'0');
	}

上面优化的程序的空间复杂度为O(1),时间复杂度为O((N-1)*(M-1));