221.最大正方形
动态规划题,还是。。
我看到这道题直接放弃。。。直接看题解,因为想了一会儿完全没思路,我连题解都看了半小时。。
如果要求最大面积,那么我们其实可以先求出能够允许的最大长度,然后最大面积直接是长度和长度的乘积就行了。
先声明一个dp,每一个元素都是是以该下标为最右下角点组成的正方形的最大长度。假如我们要求(m,n)这个点的最大长度,那么受限于(m-1,n),(m-1,n-1),(m,n-1)这三个点的最小长度的限制,即左边,上边,左上对角线的。
所以状态转移方程就找了,接下来代码就好办了。
代码如下: