剪纸次数最少的剪纸

Question

图纸上有一个m×n的矩形板。你需要把它切割成mn 1×1正方形，沿着网格直线切割。您可以将多个部分堆叠在一起，同时切割它们，这被认为是一个切割。设计一种算法，以最小的裁剪数执行此任务。任何帮助都是非常感谢的。

Answer 1

注意，每一次切割都将沿着网格线进行，而不是移动刀子，我们总是可以将纸张移动到所需的切割位置。这就意味着，如果我们有一堆纸，我们总是可以移动和堆叠每一张纸，这样我们就可以在每一张纸上独立地切割到一个想要的位置。

因此，可以用极小极大法递归求解m问题。设o(m，n)是最优方法所需的割集数。那么，最优切割是给我们两张纸，大小为a，b，c，x，d，使两者的最大切数最小化。我们总是可以并行地切割它们(正如我们在上面看到的)，所以这就是为什么只有最大的，而不是它们的最佳削减数的总和。

最后，请注意，我们只能切m或n，而不能同时切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))。