一个 × 棋盘将被切成它的 · 个单位正方形。

Question

一张 × 的棋盘要被切成单位正方形。在每一步，你可以进行横向或纵向的切割。第一个切割将把棋盘分成两个子棋盘；之后，每一次切割都会把一个剩余的子棋盘分成两个。每次切割的代价等于生成的两个子棋盘中较小的那个的单位正方形数量。例如，在一个 2×3 的棋盘上进行横向切割会得到两个 1×3 的子棋盘，代价为 3，而纵向切割会得到大小分别为 2×1 和 2×2 的子棋盘，代价为 2。切割的总代价是可累加的：一系列切割的总代价等于它们各自代价的总和。请描述一个算法来计算将棋盘切割成单位正方形的最小总代价。证明其正确性并分析其时间复杂度。

我的解决方案如下： 1. 我遵循贪心策略，检查行数 m 和列数 n 中的最大值，并进行一次切割。 2. 如果 m 更高，则进行纵向切割，否则进行横向切割。 3. 这给出了每一步最低的切割代价。 4. 我采用分治方法，递归遵循这种方法，直到得到 1x1 的单位正方形。

这似乎可以工作，但我遇到的困难是推导出我的算法的时间复杂度和证明其正确性。

我的时间复杂度表达式为 T(mn) = 2 T(mn/2) + theta(n)。

有人能告诉我如何做到这一点吗？

- Ayan Sengupta

---

这也是我所相信的。但是我还无法在数学上证明，因此没有明确说明。也许如果我能推导出复杂度，我可以尝试证明它。 - Ayan Sengupta

啊，我看错了问题。 - Daniel McLaury

Answer 1

最小成本为(n-1)*m+(m-1)*n。您可以通过进行m个水平切割，每个切割付出n-1和进行n个垂直切割，每个切割付出m-1来获得。这是一个O(1)算法。

要切断一个单位正方形，您需要在(n-1)*(m-1)种情况下至少支付2个单位的价格，在(n-1)+(m-1)种情况下至少支付1个单位的价格，并且您可以免费获得一个单位的正方形。这将从下面限制总体价格：

2*(n-1)*(m-1)+1*(n-1)+(m-1)+0*1 = 2*n*m-n-m = (n-1)*m+(m-1)*n

- Yola

---

FYI，你和Gassa的代码似乎在2-100范围内匹配i,j：https://repl.it/@gl_dbrqn/ExperiencedUnfoldedBrain - גלעד ברקן

那么你的意思是对于这种情况它是O(mn)的时间复杂度？ - Ayan Sengupta

@AyanSengupta 这是O(1)的，它是一个直接的公式！ - גלעד ברקן

Answer 2

这里是一个动态规划的方法，时间复杂度为 O (m * n * (m + n))。

对于每个可能的子矩形大小 w * h，计算将其切割成单个正方形的成本 f (w, h)。 选择第一次切割：w * h 要么被切成 a * h 和 b * h，要么被切成 w * c 和 w * d。 将 a * h 和 b * h 切割的成本为 min (a, b) * h + f (a, h) + f (b, h)。 将 w * c 和 w * d 切割的成本为 w * min (c, d) + f (w, c) + f (w, d)。 将所有这些内容整合在一起，我们得到：

f (w, h) = min of
                min {for every a such that 0 < a < w}
                    (let b = w - a)
                    min (a, b) * h + f (a, h) + f (b, h)
           and
                min {for every c such that 0 < c < h}
                    (let d = h - c)
                    w * min (c, d) + f (w, c) + f (w, d)

基础是 f(1,1)=0。

我们可以将所有的f(w,h)存储为二维数组，并在两个循环中自下而上地计算它们，就像这样：

for w = 1, 2, ..., m:
    for h = 1, 2, ..., n:
        calculate f[w][h] by the formula above in O (w + h)

或者编写一个带有记忆化的递归函数。

这两种方法都可以在O(m * n * (m + n))内完成：我们需要计算m * n个值，每个值都是O(m + n)个值中的最小值。

---

如果贪心算法确实有效（我不确定），那么它的时间复杂度为O(log m + log n)。 例如，如果m = 17且n = 23，则必须考虑以下矩形：

17 * 23
17 * 11 and 17 * 12
 8 * 11 and  8 * 12 and  9 * 11 and  9 * 12
 8 *  5 and  8 *  6 and  9 *  5 and  9 *  6
 4 *  5 and  4 *  6 and  5 *  5 and  5 *  6
 4 *  2 and  4 *  3 and  5 *  2 and  5 *  3
 2 *  2 and  2 *  3 and  3 *  2 and  3 *  3
 1 *  1 and  1 *  2 and  2 *  1 and  2 *  2
 1 *  1 again

正如我们所看到的，矩形的形式将会是 (m / 2^x) * (n / 2^y)，其中 x 和 y 的取值范围在 0 到 log_2 (m + n) 之间，取整方向可以是上取整或下取整。

- Gassa

---

我在这里尝试实现了你的算法：https://repl.it/@gl_dbrqn/BlankFreshLicense 但是当我输入 f(2,3) 时，得到的结果是13，而我认为答案应该是7。我是否有什么误解？ - גלעד ברקן

很好。我只是想与贪婪算法进行比较，所以我不关心效率，但还是谢谢你的建议！ - גלעד ברקן

FYI，你和Yola的代码似乎在2-100范围内的i,j匹配：https://repl.it/@gl_dbrqn/ExperiencedUnfoldedBrain - גלעד ברקן

@Gassa 感谢您的详细解释。我想到了动态规划，但没有采用它。让我解释一下原因。动态规划可以帮助我计算切割成本并将其存储供将来参考，这需要恒定的时间。然而，在这种情况下，当进行切割时，计算成本也需要恒定的时间，因为一个 M x N 的板子要么会变成 M x N-1 和 1 x N 的子板，要么会变成 M-1 x N 和 M x 1 的子板。在任一情况下，切割的成本都是 M 或 N，可以在恒定时间内计算出来。您认为呢？ - Ayan Sengupta

@AyanSengupta 是的，现在我明白了，我认为 Yola 的另一个答案在本质上是正确的（尽管细节上略有偏差）。作为理论下限，动态规划是过于繁琐的。因此，您可以完全忽略我的答案。动态规划的唯一好处是，在没有明显的贪心解决方案时，该方法仍将适用于其他成本函数。 - Gassa