7.6 Подсчёт замощений¶

Иногда состояния в динамическом программировании оказываются сложнее, чем просто набор нескольких чисел. В качестве примера рассмотрим задачу о подсчёте количества различных способов замостить решётку размера n × m плитками размеров 1 × 2 и 2 × 1.

Например, для поля 4 × 6 существует много корректных замощений. Один из возможных вариантов можно описать так: часть плиток лежит горизонтально, а часть — вертикально, причём всё поле покрыто полностью, без наложений и пустых клеток.

Задача состоит не в том, чтобы найти одно замощение, а в том, чтобы подсчитать общее число различных замощений.

Идея динамического программирования по строкам¶

Такую задачу можно решать динамическим программированием, проходя поле строка за строкой.

Главная мысль такая: чтобы понять, какие варианты возможны для текущей строки, достаточно знать, как была устроена предыдущая строка. Значит, можно хранить состояние строки и переходить от одной строки к следующей.

Как кодировать строку¶

Если смотреть на одну строку, каждая её клетка может находиться в одном из нескольких типов состояния:

• клетка содержит верхнюю половину вертикальной плитки;
• клетка содержит нижнюю половину вертикальной плитки;
• клетка является левой половиной горизонтальной плитки;
• клетка является правой половиной горизонтальной плитки.

То есть у каждой позиции строки есть 4 возможных типа. Поэтому всю строку длины m можно представить как последовательность из m символов, каждый из которых выбирается из 4 вариантов.

Если обозначить через count(k, x) количество способов замостить первые k строк так, что k-я строка имеет состояние x, то можно построить динамику:

• перебираем номер строки k;
• перебираем возможное состояние x текущей строки;
• суммируем все состояния предыдущей строки, которые совместимы с x.

Когда две соседние строки совместимы¶

Корректное полное замощение должно удовлетворять трём условиям:

1. в первой строке не может быть нижних частей вертикальных плиток;
2. в последней строке не может быть верхних частей вертикальных плиток;
3. каждая пара соседних строк должна быть совместимой.

Совместимость означает, что если в одной строке в некотором столбце стоит верхняя половина вертикальной плитки, то в следующей строке в том же столбце обязана стоять нижняя половина той же плитки. Аналогично, никакая нижняя половина не может появиться без соответствующей верхней половины строкой выше.

Горизонтальные плитки полностью лежат внутри одной строки, поэтому их согласованность проверяется внутри самой строки.

flowchart TD
    A[Предыдущая строка] --> B{Совместима ли с текущей?}
    B -- Да --> C[Добавляем число способов]
    B -- Нет --> D[Переход невозможен]
    C --> E[DP для следующей строки]
    D --> E

Оценка сложности в наивном представлении¶

Если в каждой клетке строки 4 возможных состояния, то всего различных строк длины m не больше, чем 4^m.

Тогда:

• для каждой из n строк мы перебираем все возможные состояния;
• для каждого состояния текущей строки перебираем все состояния предыдущей строки.

Получаем оценку:

O(n · 4^m · 4^m) = O(n · 4^(2m))

Это уже работает для маленьких m, но быстро становится слишком тяжёлым.

Более компактное представление состояния¶

Можно заметить, что для перехода между строками нам не нужно помнить полное устройство предыдущей строки. Достаточно знать только одно:

в каких столбцах из предыдущей строки вниз продолжается вертикальная плитка.

То есть для каждого столбца нам достаточно одного бита:

• 1 — сверху в этот столбец спускается вертикальная плитка;
• 0 — никакого продолжения сверху нет.

Тогда строка кодируется уже не четырьмя вариантами на клетку, а двумя. Следовательно, число состояний уменьшается до 2^m.

После этого сложность становится такой:

O(n · 2^m · 2^m) = O(n · 2^(2m))

Это заметно лучше.

Почему обычно поворачивают поле¶

В оценке сложности самый дорогой множитель зависит от m. Поэтому на практике полезно считать, что m — это меньшая сторона прямоугольника.

То есть перед решением удобно при необходимости повернуть поле местами:

• если n < m, можно обрабатывать по столбцам;
• если m <= n, можно обрабатывать по строкам.

Так мы уменьшаем число состояний и ускоряем алгоритм.

Интуиция битовой динамики¶

В компактной версии каждое состояние — это битовая маска длины m.

• Бит 1 означает: клетка в текущей строке уже занята как продолжение вертикальной плитки сверху.
• Бит 0 означает: эту клетку ещё нужно покрыть внутри текущей строки.

Дальше мы идём слева направо по строке и пытаемся заполнить все свободные клетки:

• либо ставим горизонтальную плитку, если соседняя клетка тоже свободна;
• либо начинаем вертикальную плитку, и тогда в маске следующей строки в этом столбце появится бит 1.

flowchart LR
    A[Маска текущей строки] --> B[Заполняем слева направо]
    B --> C[Горизонтальная плитка]
    B --> D[Вертикальная плитка]
    C --> E[Маска следующей строки]
    D --> E

Именно так обычно решают эту задачу в олимпиадном программировании.

Ещё одно наблюдение¶

Для задачи существует и прямая математическая формула для числа замощений прямоугольника домино-плитками. Она позволяет вычислять ответ очень быстро с теоретической точки зрения.

Однако на практике возникает проблема: в формуле участвуют вещественные числа, и нужно аккуратно хранить промежуточные результаты, чтобы избежать ошибок округления.

Поэтому в соревновательном программировании чаще используют именно динамическое программирование по профилю.

Что важно запомнить¶

Подсчёт замощений — это хороший пример задачи, где состояние ДП является не числом и не парой чисел, а целым профилем строки.

Главные идеи здесь такие:

• состояние может описывать границу между уже обработанной и необработанной частью поля;
• для перехода между строками часто достаточно хранить только минимально необходимую информацию;
• битовые маски позволяют резко сократить число состояний;
• выбор меньшей стороны прямоугольника в роли ширины профиля критически влияет на скорость решения.

Небольшой адаптированный пример¶

Пусть нужно посчитать число замощений поля 2 × 5 домино-плитками.

Обозначим dp[i][mask] — число способов корректно обработать первые i строк, если следующая строка начинается в состоянии mask.

Тогда:

• стартовое состояние: dp[0][0] = 1;
• из каждой маски строятся все допустимые маски следующей строки;
• ответом будет dp[n][0], потому что после обработки всех строк не должно остаться незакрытых вертикальных плиток.

Для поля 2 × 5 ответ равен 8.

Итог¶

В этой задаче динамическое программирование используется не по числам, а по состояниям границы. Это важный шаг к более сложным техникам, например:

• ДП по профилю;
• ДП по битмаскам;
• перебору конфигураций строк и столбцов.

Задачи такого типа хорошо тренируют умение правильно выбирать состояние и выкидывать из него всё лишнее.