统计全为 1 的正方形子矩阵

一句话套路:每个 1 格子看它正上方、正左方、左上方三个邻居,谁最小就卡住了能凑多大的正方形,取最小值加一。下面逐格填表。

先看骨架:行头是行下标 r0 到 r2,列头是列下标 c0 到 c3。表里现在显示的是原始输入(0 或 1)。我们会从左上往右下,逐格把每个 1 改写成「以它为右下角的最大正方形边长」,同时累加答案。

格子 (0,0) 本身是 0,没法当任何全 1 正方形的右下角,dp[0][0]=0,贡献 0。答案累计仍是 0。

格子 (0,1) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][1]=1,贡献 1。答案累计 = 1。

格子 (0,2) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][2]=1,贡献 1。答案累计 = 2。

格子 (0,3) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][3]=1,贡献 1。答案累计 = 3。

格子 (1,0) 是 1,但它在首列,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[1][0]=1,贡献 1。答案累计 = 4。

算 dp[1][1]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][1]=1,左方 dp[1][0]=1,左上 dp[0][0]=0。能凑出的正方形被这三个里最小的那个卡住。

三者最小值是 0,加一得 dp[1][1]=1。这格作为右下角能凑出边长 1 到 1 的正方形,共 1 个,累加进答案。答案累计 = 5。

算 dp[1][2]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][2]=1,左方 dp[1][1]=1,左上 dp[0][1]=1。能凑出的正方形被这三个里最小的那个卡住。

三者最小值是 1,加一得 dp[1][2]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 7。

算 dp[1][3]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][3]=1,左方 dp[1][2]=2,左上 dp[0][2]=1。能凑出的正方形被这三个里最小的那个卡住。

三者最小值是 1,加一得 dp[1][3]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 9。

格子 (2,0) 本身是 0,没法当任何全 1 正方形的右下角,dp[2][0]=0,贡献 0。答案累计仍是 9。

算 dp[2][1]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][1]=1,左方 dp[2][0]=0,左上 dp[1][0]=1。能凑出的正方形被这三个里最小的那个卡住。

三者最小值是 0,加一得 dp[2][1]=1。这格作为右下角能凑出边长 1 到 1 的正方形,共 1 个,累加进答案。答案累计 = 10。

算 dp[2][2]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][2]=2,左方 dp[2][1]=1,左上 dp[1][1]=1。能凑出的正方形被这三个里最小的那个卡住。

三者最小值是 1,加一得 dp[2][2]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 12。

算 dp[2][3]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][3]=2,左方 dp[2][2]=2,左上 dp[1][2]=2。能凑出的正方形被这三个里最小的那个卡住。

三者最小值是 2,加一得 dp[2][3]=3。这格作为右下角能凑出边长 1 到 3 的正方形,共 3 个,累加进答案。答案累计 = 15。

整张表填满了。每个格子里的数就是「以它为右下角的全 1 正方形个数」,把全表的 dp 值加起来 = 15,正是答案。绿格就是所有能当右下角的格子。

复盘整条思路:dp[r][c] = 以 (r,c) 为右下角的最大全 1 正方形边长,也等于该格贡献的正方形个数;1 格取上、左、左上三者最小值加一,0 格记 0;逐格相加即总数 15。

边界:单格按本值;全 0 答案 0;2x2 全 1 答案 5,各尺寸都要数到。

两个追问:和 lc221 同转移,差在 max 平方还是 sum;不许改输入就另开 dp 或滚动两行。