1277.Count-Square-Submatrices-with-All-Ones

1277. Count Square Submatrices with All Ones

题目地址

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

题目描述

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:
Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

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

代码

Approach #1 DP

Time: O(N^2) && Space: O(N^2)

class Solution {
  public int countSquares(int[][] matrix) {
        int n = matrix.length;
    int m = matrix[0].length;
    int[][] dp = new int[n][m];
    int count = 0;

    for (int i = 0; i < n; i++) 
      if (matrix[i][0] == 1)    
        dp[i][0] = 1;

    for (int j = 0; j < m; j++)
      if (matrix[0][j] == 1)
        dp[0][j] = 1;

    for (int i = 1; i < n; i++) {
      for (int j = 1; j < m; j++) {
        if (matrix[i][j] == 1) {
          int min = 1 + Math.min(dp[i - 1][j], 
                                Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
          dp[i][j] = min;
        }
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        count += dp[i][j];
      }
    }

    return count;
  }
}