2020-03-22 吴亲库里 库里的深夜食堂
在给定只包含 0 和 1 的二维矩阵中，找出只包含 1 的最大正方形面积。所以图中 demo 的值是4。
****
暴力法是可以解的，但是这辈子都不可能用暴力法的。ps:我在骗人。
之前也有专门的文章提到过动态规划 算法之动态规划。（这篇文章写于大半年以前，发现现在对动态规划又有了一点新认识）。类似最大，最小......，这种极限值一般情况下都是可以使用动态规划来解的，为什么呢？道理其实很简单，因为最大值依赖于递进的结果。这句话咋么理解？还是举上面的例子，最终的结果是4。它是一开始就直接能得出4吗？不是！在坐标(0,0)的位置，最大正方形边长是1，面积也是1。到了(2,3)的位置，最大边长为2，面积为4，之后就不存在更大的边长了。
这个过程中，需要根据之前位置的状态以及当前位置的值，更新当前状态值。并且始终存在一个全局最大边长(方便直接平方，返回结果)。
我们需要更新全局最大边长值。这个值是根据什么更新的？也就是和谁去比较？当然是和当前下标位置的最大边长(状态的定义)进行比较,当前下标边长如何算出的?(状态转移方程)，下图反映了这个过程:
dp[$i][$j] //表示下标为(i,j)时最大正方形边长dp[$i][$j]=min($dp[$i-1][$j,$dp[$i][$j-1],$dp[$i-1][$j-1])+1class Solution {
/**
* @param String[][] $matrix
* @return Integer
*/
function maximalSquare($matrix) {
$row=count($matrix);
$cols=$row>0?count($matrix[0]):0;
$max=0;
$dp=[];
for($i=1;$i<=$row;$i++){
for($j=1;$j<=$cols;$j++){
if($matrix[$i-1][$j-1]==1){
$dp[$i][$j]=min($dp[$i-1][$j],$dp[$i][$j-1],$dp[$i-1][$j-1])+1;
$max=max($max,$dp[$i][$j]);
}
}
}
return $max*$max;
}
}
