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