Количество способов сразить сетку 2xN с запрещенными позициями с домино 2×1 и 1×2?
Мне было интересно узнать алгоритм для решения этой проблемы. Формальное описание постановки задачи выглядит примерно так: дано N (<100) и домино 2х1 и 1х2 Я должен найти количество возможных вариантов сетки. Разница здесь в том, что некоторые клетки будут зачернены, чтобы обозначить запрещенную позицию.
Input:
5
01000
00010
Output:
1
0 на входе представляет пустую ячейку и 1 запрещенную ячейку.
Я нашел подобный вопрос здесь Шестигранная решетка . Хотя было небольшое упоминание о решении подобных проблем с помощью динамического программирования с помощью битовых масок, я не смог найти подробного объяснения этой техники.
PS: хотя я знаю, как решить общую проблему листов сетки, скажите, что в этой задаче, только если нам дают только пустые ячейки, рекуррентность может быть сформирована как F (n) = F (n-1) + F (n- 2) путем размещения домино 1х2 или двух домино 2х1, чтобы покрыть первый и первый два столбца соответственно. Это может быть решено итеративно или даже для больших N (скажем,> 10 ^ 7) мы можем использовать метод матричного экспонирования. Но мне интересно узнать о технике решения подобных проблем DP + битмаски. Любая помощь будет оценена.
Решение
Для i = n, n-1, …, 1 вы вычисляете f00 (i) = «Количество комбинаций для заполнения из столбца i, если в столбце i содержится 0,0», f01 (i) = «Количество комбинаций для заполнения из столбца i, если столбец i содержал 0,1 «, f10 (i) =» Количество комбинаций для заполнения из столбца i, если столбец i содержал 1,0 «, f11 (i) =» Количество комбинаций для заполнения из столбца i, если столбец я содержал 1,1 «
Очевидно, f00 (n) = f11 (n) = 1, f01 (n) = f10 (n) = 0.
F00 (я), если я < n: Вы можете использовать одну вертикальную плитку, которая находится в следующем столбце, или две горизонтальные плитки, если следующий столбец (0, 0). Таким образом, если следующий столбец (0, 0), то результатом будет f00 (i + 1) + f11 (i + 1); если следующий столбец (0, 1), (1, 0) или (1, 1), то f00 (i) = f01, f10 или f11 (i + 1).
F10 (я) для меня < n: Вы должны использовать одну горизонтальную плитку. Если следующий столбец содержит (0, 1) или (1, 1), то результат равен 0; если следующий столбец содержит (0, 0) или (1, 0), то результатом будет f01 (i + 1) или f11 (i + 1).
F01 (I) работает так же.
f11 (i) = f00, f01, f10 или f11 (i + 1) в зависимости от того, что находится в следующем столбце.
Решение легко найти за линейное время.
Другие решения