Обратите внимание, что каждый разрез будет проходить по линиям сетки, и что вместо перемещения ножа мы всегда можем переместить бумагу в желаемое место разреза. Это означает, что если у нас есть пачка листов бумаги, мы всегда можем переместить и сложить каждую бумагу так, чтобы мы могли вырезать в желаемом месте независимо от каждой бумаги. 1004 * может быть выполнено рекурсивно в минимаксном подходе. Пусть o (m, n) будет количеством разрезов, необходимых для оптимального метода. Тогда оптимальный разрез - это тот, который дает нам два листа бумаги размером axb и c xd , так что максимальное количество разрезов для них обоих сводится к минимуму. Мы всегда можем разрезать их параллельно (как мы видели выше), поэтому учитывается только максимальное, а не сумма их оптимальных разрезов.
Наконец, обратите внимание, что мы можем вырезать только 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)
И, запомнив, мы можем выполнять динамическое c программирование на m, n, что я сделал выше. Просматривая результаты этой функции, мы находим правильную последовательность A096198 . Мы также обнаружили, что существует гораздо более простое решение, а именно ceil(log2(m)) + ceil(log2(n)).