最大正方形

题目
在一个由 0 和 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,从全为1的正方形中找出最大的边长，边长的平方就是答案。

class Solution {
    public boolean allOne(char[][] matrix, int x, int y, int n){
        for(int i=x; i<=x+n; ++i){
            for(int j=y; j<=y+n; ++j){
                if(matrix[i][j] == '0') return false;
            }
        }
        return true;
    }
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length==0) return 0;
        int maxArea = 0;
        int height = matrix.length;
        int width = matrix[0].length;
        for(int i=0; i<height; ++i){
            for(int j=0; j<width; ++j){
                int n = Math.min(width-j, height-i)-1;
                // System.out.println(n);
                for(int k=0; k<=n; ++k){
                    int area=0;
                    // System.out.println(k);
                    if(allOne(matrix, i, j, k)){
                        area = (k+1) * (k+1);
                    }
                    maxArea = Math.max(maxArea, area);
                    // System.out.println(maxArea);
                }
            }
        }
        return maxArea;
    }
}

** 方法2 **
dp法

定义dp[i][j]为以i,j为右下点构成的正方形的最大边长， 最终从所有的dp中找出最大的边长就是符合题目的正方形的边长。

动态规划最重要的第二点就是如何递推，这里首先观察dp[i][j], 由于dp[i][j]定义的是以i,j为右下点的正方形，因此只考虑右上的dp与dp[i][j]的关系，显然，如果dp[i-][j], dp[i][j-1], dp[i-1][j-1]中有一个为0的话那么dp[i][j]构成的最大正方形的边长只能是1，如果dp[i-][j], dp[i][j-1], dp[i-1][j-1]都不为0的胡，也就是它们都大于等于1的话才有可能构成边长大于1的正方形，构成的正方形的边长为min(dp[i-][j], dp[i][j-1], dp[i-1][j-1])+1。

考虑到边界时, dp[0][0] 对应的左边，上边，左上也应该要有dp， 所以把dp的大小定义为原来matrix的大小+1，dp[i][j]对应的是matrix[i-1][j-1]。

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int h = matrix.length;
        int w = matrix[0].length;
        int[][] dp = new int[h+1][w+1];
        int res = 0;
        for(int i=1; i<h+1; ++i){
            for(int j=1; j<w+1; ++j){
                if(matrix[i-1][j-1] == '1'){
                    if((dp[i-1][j] != 0) && (dp[i][j-1] != 0) && (dp[i-1][j-1] != 0)){
                        dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                    }
                    else{
                        dp[i][j] = 1;
                    }
                    System.out.println(dp[i][j]);
                    res = Math.max(res, dp[i][j]);
                }
                
            }
        }
        return res*res;
    }
}