題意

給定一個由01組成的矩形，要求找出矩形內由1組成的最大正方形面積。

思路

狀態表示：d[i,j]$d[i, j]$，以位置為矩形右下角的最大正方形的邊長。r[i,j]$r[i, j]$，第i行，到第j個位置的1的長度。c[i,j]$c[i, j]$，第j列，到第i個位置的1的長度。

轉移方程：d[i,j]=min{d[i?1,j?1]+1,r[i,j],c[i,j]}$d[i, j] = min/{d[i - 1, j - 1] + 1, r[i, j], c[i, j]/}$

時間復雜度：O(n2)$O(n^2)$

代碼