本文共 1185 字，大约阅读时间需要 3 分钟。

链接：

大意：

给定一个只由'0'和'1'组成的二维字符数组，求出只由'1'组成的最大正方形的面积。例子：

思路：

采用动态规划解法。

记dp[i][j]为以该点为正方形左下角时可得到的最大正方形边长

若在某个位置[i,j]上的字符为'0'，则dp[i][j] = 0;

若在某个位置[i,j]上的字符为'1'，则需判断其左边点[i, j - 1]、上边点[i - 1, j]以及左上方对角线点[i - 1, j - 1]上的点的dp值。即以这些点作为某一正方形的左下角点时的各自的最大正方形边长。之后dp[i][j]便是取这三个数中的最小数加一。

比如对于如下的字符数组：

1 1 

1 1 

则若要求以右下角1为某一正方形的左下角端点时，首先查看上述三个点可以得到的正方形的最大边长，发现最大边长都是1。所以以右下角1为某一正方形左下角端点时可得最大正方形边长为 1 + 1 = 2

在比如对于如下字符数组：

1 1

则若要求以右下角1为某一正方形的左下角端点时，首先查看上述三个点可以得到的正方形的最大边长分别为1 0 1，3个最大边长中的最小数为0。所以以右下角1为某一正方形左下角端点时可得最大正方形边长为 0 + 1 = 1

另外，为处理数组越界问题，一般将dp数组空间比原数据数组空间增加1（二维数组则为增加一行一列）

代码：

class Solution {    public int maximalSquare(char[][] matrix) {        if (matrix.length == 0)            return 0;        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];        int max = 0; // max记录最大正方形的边长        for (int i = 1; i < dp.length; i++) {            for (int j = 1; j < dp[i].length; j++) {                if (matrix[i - 1][j - 1] == '1') {                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;                    max = Math.max(dp[i][j], max);                }            }        }        return max * max;    }}

结果：

结论：

动态规划的灵魂就是递推方程。 

转载地址：http://paesi.baihongyu.com/