[在方格纸上绘制了一个m×n的矩形板。您需要通过沿着网格线的直切将其切成mn 1×1平方。您可以堆叠几块同时切割,这被视为一次切割。设计一种算法,以最少的切割次数执行此任务。任何帮助表示赞赏
请注意,每次裁切都将沿着网格线,并且我们可以始终将纸张移动到所需的裁切位置,而不用移动刀子。这意味着,如果我们有一堆纸,我们总是可以移动并堆叠每张纸,这样我们就可以在每张纸上独立地裁切到所需的位置。
因此解决m x n问题可以通过极小极大方法来递归完成。令o(m,n)为最佳方法中需要切割的次数。然后,最佳裁切是给我们两张尺寸为[[a x b和c x d的纸的裁切,从而使两个裁切的最大裁切次数减至最少。我们总是可以并行切割它们(如上所述),这就是为什么仅最大切割而不是其最佳切割总数的原因。
最后请注意,我们只能剪切m
或n,而不能同时剪切。有了这些观察,我们可以编写一个循环(我使用Python):import functools
@functools.lru_cache(None) # Memoize solution.
def o(m, n):
if m == n == 1: return 0
cut_candidates = [((k, n), (m-k, n)) for k in range(1, m)]
cut_candidates += [((m, k), (m, n-k)) for k in range(1, n)]
return 1 + min(max(o(a, b), o(c, d))
for (a, b), (c, d) in cut_candidates)
并且通过记忆,我们可以对m, n
进行动态编程,就像我之前所做的那样。查找此函数的结果,我们找到正确的序列A096198。我们还发现有一个简单得多的解决方案,即ceil(log2(m)) + ceil(log2(n))
。