[LeetCode]1277. Count Square Submatrices with All Ones

Posted by Leo Eatle on 2020-05-21

Question

给一个 m * n 的仅包含0和1的矩阵,目的是找到这个矩阵中有多少有效的、只包含1的矩阵,比如

1 1 1
1 1 1
0 0 1

这里只有一条边的1矩阵有7个,有两条边的1矩阵有两个,所以总数是9

Solution

可以察觉到这是一个dp题,但是要如何利用到已经计算好的矩阵呢?
我们先从左上角开始,如果是1,就有1个了,如果是0,那么就没有

然后可以看旁边的,其实对于第一行和第一列的,都必不可能产生除了自己以外的新矩阵。

但是对于右下角的,确实就有可能产生一个n*n的矩阵,是否会产生,取决于它的左上、左边、上边是否也是1.

由此我们可以得到一个公式:dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
是否+1取决于自己是不是1