统计全为1的正方形子矩阵 题目描述 给定一个 m×n 的二进制矩阵（元素只包含0或1），请统计其中全部由1组成的正方形子矩阵的数量。 示例： 输入：matrix = [ [ 0,1,1,1 ], [ 1,1,1,1 ], [ 0,1,1,1 ] ] 输出：15 解释： 边长为1的正方形有10个。 边长为2的正方形有4个（位置分别是(0,1), (0,2), (1,1), (1,2)）。 边长为3的正方形有1个（位置是(1,1)）。 总共10 + 4 + 1 = 15个。 解题思路 这个问题可以用动态规划解决。我们定义dp[ i][ j ]表示以(i,j)为右下角顶点的最大正方形边长。关键思路是：一个位置能构成的正方形数量取决于它能扩展的最大边长。 详细步骤 状态定义 dp[ i][ j ]表示以(i,j)为右下角的正方形的最大边长。 状态转移方程 对于matrix[ i][ j ] = 1的位置： 如果i=0或j=0（第一行或第一列），dp[ i][ j ] = 1 否则，dp[ i][ j] = min(dp[ i-1][ j], dp[ i][ j-1], dp[ i-1][ j-1 ]) + 1 这个转移方程的含义是：一个位置能构成的正方形大小受其上方、左方和左上方三个位置的限制。 统计数量 关键点：以(i,j)为右下角的正方形数量正好等于dp[ i][ j ]的值。 例如，如果dp[ i][ j ] = 3，说明可以形成： 边长为1的正方形（右下角在(i,j)） 边长为2的正方形 边长为3的正方形 总共3个正方形。 算法流程 初始化dp数组为0，总计数count = 0 遍历矩阵的每个位置(i,j) 如果matrix[ i][ j ] = 1： 如果是边界位置：dp[ i][ j ] = 1 否则：dp[ i][ j ] = min(左、上、左上三个值) + 1 count += dp[ i][ j ]（累加所有正方形数量） 返回count 示例演算 对于示例矩阵： 初始矩阵： [ 0,1,1,1 ] [ 1,1,1,1 ] [ 0,1,1,1 ] 计算dp矩阵： [ 0,1,1,1 ] [ 1,1,2,2 ] [ 0,1,2,3 ] 统计：0+1+1+1 + 1+1+2+2 + 0+1+2+3 = 15 复杂度分析 时间复杂度：O(m×n)，只需遍历矩阵一次 空间复杂度：O(m×n)，用于存储dp数组 这个解法巧妙地利用动态规划同时计算最大边长和统计数量，是处理矩阵中正方形计数问题的高效方法。