本文主要是介绍算法49：动态规划专练(力扣1139题：最大正方形面积)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
示例 1：
输入：grid = [[1,1,1],[1,0,1],[1,1,1]] 输出：9
示例 2：
输入：grid = [[1,1,0,0]] 输出：1
这一题与算法48有点相似，但是它不能用单调栈解决这个问题。也不能用算法48的动态规划思想来解决。因为这一题是以全部为1的边组成的最大面积。也就是说中间是可以为0的。式例1就是最好的说明。
上一题用了单调栈、动态规划、暴力解。而这一题已经把前两种可能性已经排除掉了。只剩下暴力解了。那么，暴力解如何来解决这一题呢？
1. 正方形有4个顶点、4条边。只要验证每条边是否全部为1就可以了
2. 每增加一行一列，就验证新增的这些边是否全部为1就可以。如果验证不通过，没关系，继续往后验证。因为，当前新增的边并不一定就是最终的正方形边长，如果它只是最大正方形内部的一些元素而已，那我们根本不关注它是否为0.
3. 需要注意的是，正方形的上方边和左方边出现了0， 那就不能继续去判断了。因为一点正方形的左上方顶点一旦确定，那上方边长和左方边长就已经确定了延长的方向了。但是，右侧的边和下方的边是要全部遍历完，才能最后确定的。
package code04.动态规划专项训练02;/*** 力扣 1139 最大的以1为边界的正方形* https://leetcode.com/problems/largest-1-bordered-square/*/
public class Largest1BorderedSquare_04_leetcode1139暴力解 {public int largest1BorderedSquare( int[][] matrix) {if (matrix == null || matrix.length == 0) {return 0;}int row = matrix.length;int col = matrix[0].length;//全局正方形最大边长int maxSide = 0;for (int i = 0; i < row ; i++) {//当前行的每一列都作为正方形的左上角，即起始点for (int j = 0; j < col; j++) {//当前格子是否为1,为1才可能成为正方形的起始点if (matrix[i][j] == 0) {continue;}//整个二维数组中，重要有1出现，那正方形边长至少为1if (maxSide == 0) {maxSide = 1;}//行边长，列边长，两者取小。因为是正方形int p = Math.min(row - i, col - j);//当前单元格 matrix[i][j] 开始的最大正方形边长int tempMaxSide = 1;boolean flag = true;//从i,j开始 到 i+index,j+index 范围内。全部都为1，才能验证通过//start为默认边长，默认边长为1. 因为matrix[i][j] == 1for (int count = 1; count < p; count++) {//上方边长 matrix[i][j+count] == '0'//左方边长 matrix[i + count][j] == '0'if (matrix[i][j+count] == 0|| matrix[i + count][j] == 0) {break;}int addCol = j + count;int addRow = i + count;//新增的行和列，不是全部范围for (int m = 1; m <= count; m++) {//下方边长 matrix[addRow][j + m]//右方边长 matrix[i + m][addCol] == '0'if (matrix[addRow][j + m] == 0|| matrix[i + m][addCol] == 0) {flag = false;}}if (flag) {tempMaxSide = Math.max(tempMaxSide, count + 1);}else {//即使右边长、下方边长遇到0. 继续放行验证。//因为当前边长有可能不是最终正方形的边界flag = true;}}/*** 以当前单元格 matrix[i][j] 边长扩展完毕，* tempMaxSide 以matrix[i][j] 为正方形左上顶点的最大边长为* maxSide 整个区域之前最大正方形边长为*/maxSide = Math.max(maxSide, tempMaxSide);}}return maxSide * maxSide;}public static void main(String[] args) {Largest1BorderedSquare_04_leetcode1139暴力解 ss = new Largest1BorderedSquare_04_leetcode1139暴力解();//int[][] matrix = {{1,1,1}, {1,0,1},{1,1,1}};int[][] matrix = {{1,1,1}, {1,1,0},{1,1,1},{0,1,1},{1,1,1}};System.out.println(ss.largest1BorderedSquare(matrix));}
}
虽然只是暴力解，但是它只花费了5毫秒，胜率86%，已经相当的nice了。
那么，这一题是否有动态规划解法呢，答案是有。
下面来说一下动态规划的思路，以事例1为案例进行分析。
原始数组：
| 下标 0 | 下标 1 | 下标 2 | |
| 下标 0 | 1 | 1 | 1 |
| 下标 1 | 1 | 0 | 1 |
| 下标 2 | 1 | 1 | 1 |
由下往上，推算每个单元格距离底部的距离。遇到1就累加，遇到0就是0.
每个单元格下方1的数量：
| 下标 0 | 下标 1 | 下标 2 | |
| 下标 0 | 3 | 1 | 3 |
| 下标 1 | 2 | 0 | 2 |
| 下标 2 | 1 | 1 | 1 |
从右往左，推算出每个单元格右侧1的数量：
| 下标 0 | 下标 1 | 下标 2 | |
| 下标 0 | 3 | 2 | 1 |
| 下标 1 | 1 | 0 | 1 |
| 下标 2 | 3 | 2 | 1 |
1. 原始数组的0行0列为1，那么右侧有3个1， 下方也有3个1. 正方形的边长必须相等，因此两者取小。 也就是说，如果以原始数组0行0列为正方形的左顶点，那么这个正方形的最大边长肯定是小于等于3的。
2. 然后就是遍历了。最大长度为1，为2，为3，逐步验证。最终确定，最大正方形的的边长，到底是多少。
3. 在步骤1讨论的过程中，我们依旧确定了正方形上方边、左侧边的边长了。那么，下方的边、右侧的边也需要验证的。下方的边，可以通过左下方的顶点右侧1的数量来确定，必须大于步骤2讨论的边长。右侧的边可以通过正方形右上方的顶点来确定，右上方的顶点下方1的数量大于等于步骤2讨论的边长即可。
动态规划代码：
package code04.动态规划专项训练02;/*** 力扣 1139 最大的以1为边界的正方形* https://leetcode.com/problems/largest-1-bordered-square/*/
public class Largest1BorderedSquare_04_leetcode1139动态规划 {//统计每个单元格，右侧连续有几个1；下方连续有几个1；public void preHandle(int[][] matrix, int[][] rightArr, int[][] bottomArr){int rowLength = matrix.length;int colLength = matrix[0].length;bottomArr[rowLength-1][colLength-1] = matrix[rowLength-1][colLength-1];rightArr[rowLength-1][colLength-1] = matrix[rowLength-1][colLength-1];//最后一行.for (int i = colLength - 2; i >= 0; i--) {//距离底部有几个1bottomArr[rowLength - 1][i] = matrix[rowLength - 1][i];//距离右侧有几个1rightArr[rowLength - 1][i] = matrix[rowLength - 1][i] == 0 ? 0 : matrix[rowLength - 1][i] + rightArr[rowLength - 1][i + 1];}//最后一列for (int i = matrix.length - 2; i >= 0; i--) {//距离底部有几个1bottomArr[i][colLength - 1] = matrix[i][colLength - 1] == 0 ? 0 : matrix[i][colLength - 1] + bottomArr[i + 1][colLength - 1];//距离右侧有几个1rightArr[i][colLength - 1] = matrix[i][colLength - 1];}for (int i = matrix.length -2; i >= 0; i--) {for (int j = matrix[0].length - 2; j >= 0; j--) {if (matrix[i][j] == 1) {bottomArr[i][j] = matrix[i][j] + bottomArr[i+1][j];rightArr[i][j] = matrix[i][j] + rightArr[i][j + 1];}}}}public int largest1BorderedSquare(int[][] matrix) {if (matrix == null || matrix.length == 0) {return 0;}int row = matrix.length;int col = matrix[0].length;int[][] rightArr = new int[row][col];int[][] bottomArr = new int[row][col];//预处理数组preHandle(matrix, rightArr, bottomArr);//全局正方形最大边长int maxSide = 0;for (int i = 0; i < row ; i++) {//当前行的每一列都作为正方形的左上角，即起始点for (int j = 0; j < col; j++) {//当前格子是否为1,为1才可能成为正方形的起始点if (matrix[i][j] == 0) {continue;}//整个二维数组中，重要有1出现，那正方形边长至少为1if (maxSide == 0) {maxSide = 1;}//行边长，列边长，两者取小。因为是正方形int sideLength = Math.min(rightArr[i][j], bottomArr[i][j]);boolean flag = true;for (int m = 1; m < sideLength; m++) {//正方形的右上顶点往下数，即右边边长int rightLength = bottomArr[i][j + m];//正方形的底部边长int bottomLength = rightArr[i + m][j];//当前边长int length = m + 1;if (rightLength >= length && bottomLength >= length) {maxSide = Math.max(maxSide, length);}}}}return maxSide * maxSide;}public static void main(String[] args) {Largest1BorderedSquare_04_leetcode1139动态规划 ss = new Largest1BorderedSquare_04_leetcode1139动态规划();//int[][] matrix = {{1,1,1}, {1,0,1},{1,1,1}};int[][] matrix = {{1,1,1}, {1,1,0},{1,1,1},{0,1,1},{1,1,1}};System.out.println(ss.largest1BorderedSquare(matrix));}
}
7毫秒，50%的胜率，也还可以了。
虽然这一题也有动态规划，但是，它是基于暴力解逐步演化过来的。暴力解法时间复杂度为 O（N^4）。我们基于暴力解在讨论边长的过程中还需要一次遍历，通过数组预处理的的方式提前进行了统计，简化了验证新增列的验证。因此，动态规划的时间复杂度为 O(N^3) + O(N^2). 实际就是O(N^3)。
这一道题，动态规划的性能比暴力解的还要低一些，虽然动态规划的时间复杂度为O(N^3)，而暴力解的时间复杂度为O(N^4)。
动态规划的时间复杂度为O(N^3)，但是，它还有一个O(N^2)预处理数组的过程。因为力扣数据量有限，动态规划时间复杂度虽然降低了一阶，但是直观看起来还是没有暴力解高。
随着数据量的增大，动态规划还是要优于暴力解的。
这篇关于算法49：动态规划专练(力扣1139题：最大正方形面积)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
