LeetCode 1277. Count Square Submatrices with All Ones

Problem

LeetCode 1277. Count Square Submatrices with All Ones

1. 题目简述

给出一个m x n的矩阵，问有多少个正方形子矩阵是都由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. 

2. 算法思路

Brute Force：

暴力解法，这种方式就是遍历所有的可能的正方形的长度，范围从1到min(m, n)，然后再遍历所有的可能的位置，如果符合条件，则count+1，最后返回count。这种方式显然速度很慢，时间复杂度为O(mn * min(m, n))。

Dynamic Programming：

这道题的DP思路我也是没有想到的，我们假设F(i, j)为以(i, j)为右下角的正方形的个数，则有如下推导：

$$F(i, j) = min(F(i - 1, j), F(i - 1, j - 1), F(i, j - 1)) + 1$$

记住吧就，想象一下很简单就能得出该公式是正确的，但是没遇过很难想到。

3. 解法

1. DP大法好

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length, res = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] > 0 && i > 0 && j > 0) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                } else {
                    dp[i][j] = matrix[i][j];
                }
                res += dp[i][j];
            }
        }

        return res;
    }
}