【算法】最大正方形问题

 虽然棋棋写的都是浅显的东西，不能同那些大佬相提并论，但始终要加油，加油，加加油，毕竟最初的目的是为了自己而记录的。

 记一次动态规划算法——最大正方形问题。

题目描述

给定一个由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
测试案例2：
输入：
{{'1','1','1','0','0'},
 {'1','1','1','1','1'},
 {'1','1','1','1','1'},
 {'1','0','0','1','0'},
 {'1','0','0','1','0'}}
测试案例3：
输入：
{{'1','1','1','1'},
 {'0','1','0','1'}}
输出：
1
测试案例4：
输入：
{{'1','0','1','1','1','1','1','0','0','0','1','0','0','0'},
{'1','0','1','1','1','0','0','0','0','0','0','0','0','0'},
{'1','0','1','0','1','1','1','0','0','0','1','0','0','0'},
{'1','1','0','1','1','1','1','0','1','0','1','0','1','0'},
{'1','1','1','1','1','1','1','0','0','0','1','0','0','0'},
{'1','0','1','1','1','1','1','1','1','0','1','1','1','0'},
{'1','0','1','1','1','1','1','1','1','1','1','1','1','0'},
{'1','0','1','1','1','1','1','1','1','1','1','1','1','0'},
{'1','1','0','1','1','1','1','1','1','1','1','1','0','0'},
{'1','0','1','1','0','1','1','1','1','1','1','1','1','0'},
{'1','0','1','1','0','1','1','1','1','1','1','1','1','1'},
{'1','0','1','1','0','1','1','1','1','1','1','1','0','0'},
{'1','0','1','1','0','1','1','1','1','1','1','1','0','0'},
{'1','0','1','1','0','1','1','0','1','0','1','1','0','0'},
{'1','0','1','1','0','1','1','0','0','0','1','1','0','0'}}
输出：
49

解题思路：

说明：

黑色：上轮查找后满足条件的点。

黄色：本次查找过程中，满足条件的点。

红色：本次查找过程中，不满足条件的点。

思路1：

暴力破解（效率低，不推荐使用）：从左到右，自上到下进行遍历，找到以每个点为正方形右下角的最大正方形边长。不说很多公式推导，直接上图，以某个点为例进行说明，其余的点都可以使用同样的方式。

第1次查找，发现目标点满足要求，继续下一次查找。

第2次查找，边长扩大1，本次需要检验的范围是2×2。发现也全部满足，继续下一次查找。

第3次查找，边长继续扩大1，所以本次的正方形为3×3，咦，有一个不满足条件，那么基于这个点为右下角的最大边长就是2。

思路2：暴力破解着实显得有点浪费资源啊，明明第一次已经校验通过的，为什么扩大后又要再校验一次。所以思路2就是在思路1的基础上，站在前人的经验结论继续深造（即前一次确认有效的就不用再校验了，可以直接拿过来使用）。

设d_xy为以(x,y)的右下角的最长正方形边长。

假设目标点d_xy的左上角d_(x-1)(y-1)的结果为2（当然也可以是其他的值），可以得出d_xy的最大值就是d_(x-1)(y-1)+1。

第1次查找，目标大小1×1，目标满足。

第2次查找，目标大小2×2，看图中可以很明白可以看出来，此次只要检验平行于x轴的一个点，以及平行于y轴的一个点即可，相较于“暴力破解”减少了2次校验。

第3次查找，目标大小3×3，这次继续校验2个点即可，如果满足，那么d_xy=3，如果不满足d_xy=2。

 总结：思路2与思路1相比，思路2每次查找只要校验2个单元格，但是思路1每次都要找n*n个单元格（可能有人会说，也利用上次，那也要校验n*n-(n-1)*(n-1)次）。

最后贴上我的代码：

 1     private final char zero='0';
 2     public int getMaxSquare(char[][] matrix, int x, int y, int targetLenth){
 3         if (matrix[x][y] == zero){
 4             return 0;
 5         }
 6         int maxSquareSideX = 1, maxSquareSideY=1;
 7         for (int i=x-targetLenth; i){
 8             if (matrix[i][y] != zero){
 9                 maxSquareSideX++;
10             }
11         }
12         for (int j=y-targetLenth; j){
13             if (matrix[x][j] != zero){
14                 maxSquareSideY++;
15             }
16         }
17         return Math.min(maxSquareSideX,maxSquareSideY);
18     }
19     /**
20      * 最大正方形
21      * @param matrix char字符型二维数组
22      * @return int整型
23      */
24     public int solve (char[][] matrix) {
25         int x=matrix.length;
26         int y=matrix[0].length;
27         int lastValue, maxSide = zero;
28         int dp[][] = new int[x][y];
29         //初始化x轴
30         for (int i=0; i){
31             dp[i][0] = matrix[i][0];
32             maxSide = Math.max(maxSide, dp[i][0]);
33         }
34         //初始化y轴
35         for (int i=0; i){
36             dp[0][i] = matrix[0][i];
37             maxSide = Math.max(maxSide, dp[0][i]);
38         }
39         //以dp[i][j]作为右下角，值为边长
40         int side;
41         for (int i=1;i){
42             for (int j=1;j){
43                 lastValue = matrix[i-1][j-1];
44                 if (lastValue > zero &&
45                         matrix[i][j] > zero &&
46                         (side=getMaxSquare(matrix, i, j, dp[i-1][j-1]-zero) + zero) > zero){
47                     dp[i][j] = side;
48                     maxSide = Math.max(maxSide, dp[i][j]);
49                 }else {
50                     dp[i][j] = matrix[i][j];
51                 }
52             }
53         }
54         return (maxSide-zero)*(maxSide-zero);
55     }