最大正方形暴力+动态规划

题目：

思路：

　　1 暴力：从每一个单元格出发每次在下方右方新作一行一列进行判断是否满足条件

　　2 动态规划：

　　　　dp[i][j]由其上方、左方和左上方的三个相邻位置的dp值决定

　　　　当前位置的元素值等于三个相邻位置的元素中的最小值加 1

　　　　根据题目分析状态转移方程：

　　　　dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1

（一）代码暴力

class Solution {

    public int maxSide = 0;

    public int maximalSquare(char[][] matrix) {

        //最大正方形，遍历每一个单元格，从每一个单元格 向下 向上 斜向下
        for(int i = 0 ; i < matrix.length ; i++){
            for(int j = 0 ; j < matrix[0].length ; j++){
                if(matrix[i][j] == '1'){
                    getMaxNum(i,j,matrix);
                }
            }
        }
        return maxSide * maxSide;
    }

    public void getMaxNum(int x, int y , char[][] matrix){

        // 遇到一个 1 作为正方形的左上角
        maxSide = Math.max(maxSide, 1);
        // 计算可能的最大正方形边长
        int currentMaxSide = Math.min(matrix.length - x, matrix[0].length - y);
        for (int k = 1; k < currentMaxSide; k++) {
            // 判断新增的一行一列是否均为 1
            boolean flag = true;
            if (matrix[x + k][y + k] == '0') {
                break;
            }

            //这块 important  注意复习
            for (int m = 0; m < k; m++) {
                if (matrix[x + k][y + m] == '0' || matrix[x + m][y + k] == '0') {
                    flag = false;
                    break;
                }
            }
　　　　　　　

            if (flag) {
                maxSide = Math.max(maxSide, k + 1);
            } else {
                break;
            }
        }

    }
}

（二）动态规划还是用算法写起来爽慢慢练吧

class Solution {

    public int maximalSquare(char[][] matrix) {

        int max = 0;
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return max;
        }
        //动态规划
        //分析状态转移方程为 dp[i][j] = min(dp[i-1][j-1],dp[i-1][j] + d[i][j-1]) + 1
        //注意在for中初始化dp[i][j] 含有0的下标 内容为1
        int[][] dp = new int[matrix.length][matrix[0].length];
        for(int i = 0 ; i < matrix.length ; i++){
            for(int j = 0 ; j < matrix[0].length ;j++){
                if(matrix[i][j] == '1'){
                    //最左上方的 i ==0 || j == 0 初始化为1
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                    }
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max * max;
    }
}

　　　　　　　　路在何方

最大正方形 暴力+动态规划

最大正方形暴力+动态规划