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.

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

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