题目链接

关键词

解析

• 状态定义：dp[i][j]: 以 matrix[i][j] 为右下角点的正方形的边长

• 状态方程：dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

• 当一个点是一个正方形的最右下角的点时，有以下的特点：
• 以该点为右下角的最大正方形的边长，比它的上方、左方和左上方为右下角的最大正方形的边长多1
• 如果该点为1且其上方、左方和左上方三个点所在的三个正方形大小相等，则它们可以合并成一个更大的正方形
• 否则，只能取它们中最小的正方形的边长加1
• 如果该点在原矩阵中本身就是0，则该点为右下角的最大正方形的边长为0

代码

相似题目