LeetCode简易题解--221（Java让你在一分钟内妙解一题）

题目描述：给定二维0，1串的矩阵，找出最大的正方形的只有1串的区域。
例如：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

答案为4.

解题思路：动态规划。
dp[i][j]是以（i，j）为右下角顶点的最大正方形的边长。

矩阵从左到右、从上到下进行扫描，当发现：
1. (i, j), (i-1, j), (i, j-1)三个位置都为1的时候，(i, j)这个值能够与这个值左边上边的某个大小的区域组成一个矩阵。例如：

1 0 1 0 0
1 0 1 1 1
1 1 1 1

接下来扫描(2, 4)，发现(i, j), (i-1, j), (i, j-1)三个位置都为1，那么(i, j)这个值能够与另外五个1构成一个矩阵。
但是题目要求的是正方形的大小，因此还要找出dp(i-1, j-1), dp(i-1, j), dp(i, j-1)中的最小值min，这个最小值是以这三个值为右下角顶点的三个正方形中的最小边长，而扫描(i, j)这个值我们发现它能够补成一个更大的矩阵，因此这个补上之后最小正方形的边长必定能够增加1，因此令dp(i, j) = min + 1.
之所以要找dp(i-1, j-1), dp(i-1, j), dp(i, j-1)中的最小值，是因为补上的是一个矩阵，而矩阵的宽限制了正方形的边长。
2. (i, j), (i-1, j), (i, j-1)三个位置有一个为0时，肯定无法补成一个矩形,因此dp(i, j) = 0.

扫描过程中，变量res纪录了所找到的最大的正方形的边长。

最终代码如下：

class SoluTIon {

public：

int maximalSquare（vector《vector《char》》& matrix） {

if（matrix.size（） == 0） return 0;

int row = matrix.size（）， col = matrix［0］.size（）;

int res = 0;

vector《int》 dp（col， 0）;

// first row

for（int i = 0;i 《 col;i++） dp［i］ = matrix［0］［i］ - ‘0’;

res = max（res， *max_element（dp.begin（）， dp.end（）））;

// dp

for（int i = 1;i 《 row;i++） {

// first col

dp［0］ = matrix［i］［0］ - ‘0’;

// other cols

for（int j = 1;j 《 col;j++） {

if（matrix［i］［j］ == ‘1’） {

int temp = min（dp［j］， dp［j-1］）;

dp［j］ = temp + （matrix［i-temp］［j-temp］ - ‘0’）;

} else {

dp［j］ = 0;

}

}

res = max（res， *max_element（dp.begin（）， dp.end（）））;

}

return res * res;

}

};