矩阵中的最小分裂数

Question

有一张长方形的薄片，里面有宽x高的方形瓷砖。薄板可以被分成两个矩形的碎片，从边缘，水平或垂直。

例如，2x2页可以分为两个2x1部分，但不能分成两个部分，其中一个是1x1。纸张可以被划分多少次，我们想要多少。

我想要创造至少一件，其中包括确切的T瓷砖。如何找到达到这一目标所需的最小数目的拆分操作？

例如。如果，宽度=5，高度=4，T= 8，那么最小的分裂数=？

第一次分裂将有两个部分: 2x4，3x4。2x4 =8，等于T.分裂数= 1。

我有蛮力的解决方案，通过它，我可以找到在一张纸中获得T瓷砖所需的最小分裂数，但我正在寻找优化的一个。有什么帮助或建议吗？

Answer 1

让n和m成为板的宽度和高度。

1. 如果T> n*m，则所需的分裂显然是不可能的。
2. 如果n或m除以T，那么我们可以很容易地进行一次分裂。请注意，也只有当T被n或m可除时，只有一次分裂就足够了。还有一个特殊情况--当T= n*m时，我们就不需要做任何分裂了。
3. 在其余的情况下，如第2条所述，我们必须至少进行两次分裂。如果T= a*b对于某个<= n和b <= m，那么我们可以进行一次分裂来获得一个大小为x的矩形，然后另一个分裂得到一个x。所以现在我们必须迭代所有可能的对(a，b)，使T= a*b。如果其中有一对矩形a可以放进一个大小为n的板中，那么我们就可以响应出答案是两个分裂。如果找不到这样的对，那么如果T是一个大素数，那么分裂是不可能的，就像情况1一样。

在某些情况下(即1和2)解决方案的复杂性。是O(1)，但在一般情况下(3.)这是O(sqrt )，因为当我们检查所有对(a，b)时，a*b =T，那么MIN(a，b) <= sqrt(T) --这也是在搜索某个数的除数时常用的技巧。