题目：
思路：
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; } }
路在何方