1. 最大正方形

个人思路，0s想出思路，二维前缀和+for nm len 遍历 n^3也能过

这里正解是dp，但是我是感觉这个dp理解起来很费解，感觉很难了。他这个dp ij表示的是边长，因为正方形面积实际上是和边长挂边的，但是边长更简单
不用开根号。然后这里你表达的是最大的边长，这里来看的话，我理解你可能会由i-1 j-1 i-j&j-1这三个正方形转化而来
110
110
001
比如这个，那就是i-1&j-1
011
011
001 这里就是i-1
110
110
001 这里就是j-1
但是实际上能走到扩大的只有
111
111
111
因为这三实际上是相互影响的。你如果i-1能扩展到i，那意味着，你这个i-1上面必须至少全部都是1，同理j-1,i-1&j-1要拓展过来，你这部分都得是1
那很明显，那就是这三的最小值都得满足满1，然后才能+1
那这里dpij >= min(这三个)+1
那这里dp ij 能不能不止+1 能+2呢？假设这个最小值是m，然后这个如果dpij >= m+2，那这里就会存在m+2，m+2，这个正方形，它这里面能拆出三个m+1
那这里也就是说，min(这三个)>=m+1，和最小值m矛盾了

我说这个证明我是感觉真反人类，照我这么理解的话，那你首先得猜出来这个m+1，然后反证证明<m+2 然后得出确实是m+1，这个这么搞我感觉难度真的是hard中的hard了

就这样吧。反正也不是以前打比赛的时候了，说实话，打比赛我感觉我都没这么推过。。。哎，大学真是三分钟热度，真的懒懒懒狗一只啊无语了。。。算了。。。今天到此为止吧，这个dp确实开动脑筋了