algorithm - 大小为 MxN 的矩阵中大小为 AxB 的子矩阵的数量

Question

我正在关注https://taninamdar.files.wordpress.com/2013/11/submatrices3.pdf查找矩阵的子矩阵总数。但是我卡住了如何查找矩阵中存在多少给定大小的子矩阵。 另外 0<=A<=M 和 0<=B<=N。
其中 AxB(子矩阵大小)和 MxN(矩阵大小)。

Answer 1

我没有阅读pdf(数学和我不是 friend )，但是这里简单的逻辑就足够了。简单地说，尝试减少维度:在长度为 n 的向量中可以放入多少个长度为 m 的向量？

答案:n-m+1。为了说服你，只需通过案例即可。假设n = 5 和m = 5。你有一种可能性。使用 n = 5 和 m = 4，您有两个(第二个向量从索引 0 或索引 1 开始)。使用 n = 5 和 m = 3，您将得到三个(向量可以从索引 0、1 或 2 开始)。对于 n = 5 和 m = 1，您得到 5，这似乎符合逻辑。

因此，为了将其应用于矩阵，您必须添加一个维度。你是怎样做的 ？乘法。长度为 n 的向量中可以放入多少个长度为 a 的向量？ n-a+1。长度为 m 的向量中可以放入多少个长度为 b 的向量？ m-b+1。

那么，在长度为 N*M 的矩阵中可以放入多少个 A*B 大小的矩阵？ (N-A+1)*(M-B+1)。

所以，我没有处理其中一个维度为0的情况。这取决于你如何考虑这种情况。