algorithm - 矩阵中可能的矩形数量

Question

我正在通过一种计算矩阵区域总和的算法。我阅读了一个预先计算总和以获得更好结果的解决方案。我想计算大小为 mXn 的二维矩阵中矩形（子 Maxtix）的可能数量。

任何人都可以使用排列和组合来解释解决方案。

Answer 1

首先从最简单的情况开始：

Start with m x n, thats 1 rectangle.
Reduce n by 1, that gives another 2.
Reduce n by 1, that gives another 3.
Reduce n by 1, that gives another 4.

你看到图案了吗？

当 n 下降到 1 时，从 m 中减去 1，然后重新开始：

Start with m-1 x n, thats 2 rectangles.
Reduce n by 1, that gives another 4.
Reduce n by 1, that gives another 6.
Reduce n by 1, that gives another 8.

你看到模式了吗..？

现在您推断出 m-2、m-3、m-4、...、1。

现在从头开始减少 n，然后是 n（或者简单地将所有结果加倍，除了 mxn）。

所有这些结果的总和就是你的答案。

Answer 2

这不是算法，而是计数问题。尝试计算 1X1 矩阵和 1X2 2X1 3X2 等矩形的数量，然后你会看到

num_of_rect(mXn) = sum(i*j) for 0<i<m+1; 0<j<n+1

---

在蟒蛇中：

def countRect(n,m):
    return sum([i*j for i in xrange(n+1) for j in xrange(m+1)])

if __name__ == "__main__":
    print countRect(2,3)

给18

Answer 3

您可以通过简单地选择要包含的行和列来计算所有矩形 a*b 和 a,b>=2（见图）：

C(m,2)*C(n,2)

您可以通过 a>=2 计算 a*1 矩形

C(m,2)*n

和 1*b 矩形 b>=2 通过

m*C(n,2)

和 1*1 矩阵通过：

m*n

所以添加这些作为最终答案：

C(m,2)*C(n,2) + C(m,2)*n + m*C(n,2) + m*n

Answer 4

mxn 矩阵中任意大小的可能矩形的数量

mn + (m-1)(n-1) + (m-2)(n-1) + .. + (m-m+1)(n-1) + (m-1)(m-2) + .. + (mm)(nn)

Sum { i * j } for i in [0,m]; j 在 [0,n]