552，动态规划解统计全为1的正方形子矩阵

Original 博哥数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

If well used, books are the best of all things; if abused, among the worst.

如果利用得当，书籍就是最好的朋友；反之，如果滥用，它就会变成最坏的东西了。

问题描述

来源：LeetCode第1277题

难度：中等

给你一个m*n的矩阵，矩阵中的元素不是0就是1，请你统计并返回其中完全由1组成的正方形子矩阵的个数。

示例 1：

输入：matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
输出：15
解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

提示：

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

动态规划解决

这题和《530，动态规划解最大正方形》解法类似，不过不同的是第530题让求的是最大正方形的面积，而这题要求的是正方形的个数。我们还按照第530题的方式来解

定义二维数组dp[i][j]，其中dp[i][j]表示的是在矩阵中以坐标(i,j)为右下角的最大正方形边长。

那么递推公式就是（不明白的可以看下第530题，这里就不在重复介绍）

dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;

并且以坐标(i,j)为右下角的正方形个数就是dp[i][j]，画个图来看一下

所以这题就简单了，我们只需要把530题的答案拿过来，然后把所有dp[i][j]值不等于0的累加即可，来看下代码

 1public int countSquares(int[][] matrix) {
 2    int count = 0;//正方形的个数
 3    int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
 4    for (int i = 0; i < matrix.length; i++) {
 5        for (int j = 0; j < matrix[0].length; j++) {
 6            //如果当前坐标是0，就不可能构成正方形，直接跳过
 7            if (matrix[i][j] == 0)
 8                continue;
 9            //递推公式
10            dp[i + 1][j + 1] = Math.min(Math.min(dp[i + 1][j], dp[i][j + 1]), dp[i][j]) + 1;
11            //累加所有的dp值
12            count += dp[i + 1][j + 1];
13        }
14    }
15    return count;
16}
17