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

题目描述

给你一个 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

解法一：动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func min(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num < res {
            res = num
        }
    }
    return res
}

func countSquares(matrix [][]int) int {
    h, w := len(matrix), len(matrix[0])
    dp := make([][]int, h)
    for i := 0; i < h; i++ {
        dp[i] = make([]int, w)
    }
    ans := 0
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if  i == 0 || j == 0 {
                dp[i][j] = matrix[i][j]
            } else if matrix[i][j] == 1 {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            }
            ans += dp[i][j]
        }
    }
    return ans
}