amxn网格上存在多少个子矩形

Question

给定m x n网格,这样的网格上存在多少个唯一的子矩形？

例如,

1 x 1 网格有1个子矩形.

1 x 2 网格有3个子矩形.

我正在寻找一个可用于直接计算现有子矩形数的通用公式.

Answer 1

答案是m(m+1)n(n+1)/4.

矩形由其在x轴和y轴上的两个投影定义.

x轴上的投影:对的数量(a,b)使得1 <= a <= b <= m = m(m + 1)/ 2

y轴的同义词

Answer 2

与@Thomash提供的答案相同,但有更多解释,张贴后代:

如果你可以在一个维度上解决这个问题,那么很容易将其移到二维.

我们来看看1x5:

 5 1x1 squares
+4 1x2 squares
+3 1x3 squares
+2 1x4 squares
+1 1x5 squares = 15 squares.

这个公式很简单:sum = n(1 + n)/ 2.在5的情况下,你想要5(1 + 5)/ 2 = 15.

所以,要获得答案,只需对n和m执行此操作,然后将它们相乘:

sumN = n(1+n)/2
sumM = m(1+m)/2
totalRectangles = nm(1+n)(1+m)/4

Answer 3

我找到了一个很好的解决方案，
让我们看看网格的表格边框。
为了创建一个矩形，我们需要边界上的四个点。
水平 2 点，垂直 2 点

例如 (n = 4, , m = 5)
请注意，选择是针对 N + 1 和 M + 1 因为我们查看的是边框而不是矩形本身

这是一个选择的例子：

我们可以使用二项式公式计算选择 2 个水平点和 2 个垂直点的所有可能选择：