Jul 11, 2020 · 6 min read
Есть два типа фигур: домино и тримино (треугольное домино):
Фигуры можно вращать. Задача — найти сколько различных вариантов замостить всю доску размером 2xN так, чтобы получилась плитка: каждый квадрат должен быть заполнен. Ответ вернуть по модулю 10^9+7.
Есть ограничения на размер N → [1, 1000].
Решение #
Сперва надо понять, что значит «различные варианты»: первое, о чём имеет смысл спрашивать интервьюера, привести примеры поворотов и уточнить они различные или нет.
Допустим есть фигура, расположенная горизонтально. Попробуем повернуть её сперва по часовой стрелке, потом против.
Как видно, получаем тот же самый вариант, если представить, что все домино без точек, выглядят одинаково.
Рассмотрим тривиальные случаи. Сколько есть различных вариантов для доски 2x1? Только один — поставить одну фигуру вертикально (горизонтально не повернуть, не хватает ширины доски).
Сколько для доски 2x2? Поставить две фигуры вертикально или горизонтально, т.е. два. По аналогии с поворотом одной фигуры, 4 различных вращения будут давать только 2 различных варианта.
Итак, идём дальше, при попытке решить задачу для N=3 начнёт вырисовываться и сам алгоритм.
3 варианта с домино.
И ещё два — с тримино. Итого, 5 различных вариантов.
На что похожи эти картинки со стрелочками? Это дерево. Узел это определённое состояние доски для какого-то столбца N, связь — возможность перехода к N+1 так, чтобы все клетки на N-м столбце оказались заполненными.
Задача сводится к подсчёту путей от корня к листьям, т.е. количества листьев.
Каким образом это можно сделать? Поиск в глубину. Запускаем рекурсивный перебор всех узлов от корня, как только дошли до листа — увеличиваем счётчик, дальше идти некуда, базовый случай. Рекурсия обойдёт все дерево.
Прежде чем писать это решение стоит оценить сложность и убедиться, что интервьюер с этим ок. Сложность линейная относительно количества узлов в дереве, вопрос только в том сколько этих узлов и как их количество меняется относительно N. Спойлер: всё очень плохо.
Представим, что мы заполнили первую колонку, и дальше есть ещё 2 свободные. Тогда можно положить одно вертикальное или два горизонтальных домино, или одно тримино в двух поворотах — 4 варианта:
А ещё можно было заполнить две колонки тримино, и дальше есть ещё 2 свободные, тогда варианты следующие:
И так на каждом уровне, по мере роста N. Чувствуете комбинаторный взрыв? Получается количество узлов в этом дереве можно оценить как O(4^N): для каждого узла может быть не более 4 деток на следующем уровне.
Для N = 1000, такое решение ни в какие ограничения не уложится. Однако, всё равно имеет смысл его написать и перейти к оптимизации.
/**
* @param {number} N
* @return {number}
*/
var numTilings = function(N) {
const mod = 1e9 + 7;
// Функция обхода дерева,
// принимает текущую колонку и некий стейт,
// показывающий состояние следующей колонки.
// Всего есть 4 состояния:
// - 0 - обе клетки в колонке свободны
// - 1 — верхняя клетка в колонке занята, нижняя свободна
// - 2 — нижняя клетка в колонке занята, верхняя свободна
function dfs(col, state) {
// Описываем 4 угла очередной секции:
// {l,r} {t,b}
// ^ левый или правый ^ верхний или нижний
// lt, lb могут быть заняты в следствии того
// как мы положили предыдущие фигуры
const lt = !(state & 1);
const lb = !(state & 2);
// rt, rb могут быть заняты
// только если мы дошли до края доски
const rt = col + 1 <= N;
const rb = col + 1 <= N;
// базовый случай → успешно дошли до конца доски,
// т.е. до листа дерева, надо вернуть единицу,
// «один вариант» заполнить всю доску
// _ x
// _ x <- край доски
// ^
// последняя колонка
if (lt && lb && !rt && !rb) {
return 1;
}
let result = 0;
// Запускаем переход в другие узлы дерева
// только если «переход возможен»,
// помним, что надо обеспечить такое
// размещение фигур чтобы не было пропусков.
// Обратите внимание на state для каждого из вызовов:
// следим за клетками следующей колонки,
// какие окажутся заняты, в зависимости
// от того какую фигуру и с каким поворотом кладём
// _ _
// _ _
// две колонки свободные
if (lt && lb && rt && rb) {
// см. картинку выше,
// я нарисовал эти переходы
result += dfs(col + 1, 0);
result += dfs(col + 1, 1);
result += dfs(col + 1, 2);
result += dfs(col + 2, 0);
}
// x _
// _ _
// левый верхний угол занят
if (!lt && lb && rt && rb) {
result += dfs(col + 1, 2);
result += dfs(col + 2, 0);
}
// _ _
// x _
// левый нижний угол занят
if (!lb && lt && rt && rb) {
result += dfs(col + 1, 1);
result += dfs(col + 2, 0);
}
return result % mod;
}
// запускаем обход от «корня дерева»:
// когда есть одна колонка (col = 1) и она пустая (стейт = 0)
return dfs(1, 0);
};Теперь надо понять где совершается лишняя работа.
Если распечатать аргументы (col, state), то становится видно, что в цепочке вызовов попадаются одни и те же пары. Функция обхода зависит только от этих аргументов, соответственно и результат для определённой пары будет всегда одинаковым, то что называют «чистая функция».
Получается, в нашем дереве есть поддеревья-клоны — в разных частях дерева могут быть узлы, начиная с которых все рекурсивные вызовы в точности повторятся, т.е. дадут ровно такое же поддерево. Это и есть лишняя работа.
Поможет мемоизация — заводим кэш куда будем записывать результаты вычислений для различных пар аргументов и читать, если вдруг встретилась уже известная пара.
/**
* @param {number} N
* @return {number}
*/
var numTilings = function(N) {
const mod = 1e9 + 7;
+ const cache = new Array(N + 2).fill(0).map(
+ () => new Array(3)
+ );
function dfs(col, state) {
+ if (cache[col][state] !== undefined) {
+ return cache[col][state];
+ }
// ...
+ cache[col][state] = result % mod;
- return result % mod;
+ return cache[col][state];
}
// запускаем обход от «корня дерева»:
// когда есть одна колонка (col = 1) и она пустая (стейт = 0)
return dfs(1, 0);
};При таком подходе мы не сможем обойти узлов больше, чем есть возможных пар (col, state), т.е. 3 * (N + 1). Отлично, сложность — линейная, O(N). По времени, и по памяти, т.к. пришлось завести кэш + стек рекурсивных вызовов.
На этом месте, скорее всего, интервью успешно закончится. Однако, эта задача хороша тем, что есть т.н. “bar raiser” — можно поднять планочку.
То, что я сейчас написал ещё называют “top-down” вариант динамического программирования, а есть “bottom-up”. Когда на основе решения задачи для некоторого K можно получить решение K+1. Таким образом, зная тривиальное решение (базовый случай), можно добраться до указанного в условии N.
По времени получится так же линия, а вот по памяти можно получить O(1). Именно это и могут попросить написать. Вся сложность вывести рекуррентное соотношение.
Если есть желание увидеть разбор такого решения — дайте знать, напишу вторую часть поста.
UPD (16.07.2020) Спасибо @d_dudkevich за то, что указал на ошибку на одной из схем. Смело пишите в чат, если заметили, что что-то не сходится :-)
PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗
Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.