Мне очень хотелось узнать алгоритм решения этой задачи. Формальное описание постановки задачи выглядит примерно так: Имея N(‹100) и костяшки домино 2x1 и 1x2, я должен найти количество различных возможных замощений сетки. Разница здесь в том, что некоторые ячейки будут зачернены, чтобы обозначить запрещенную позицию.
Input:
5
01000
00010
Output:
1
0 во входных данных представляет собой пустую ячейку и 1 запрещенную ячейку. Я нашел аналогичный вопрос здесь Разбиение на шестиугольные сетки . Хотя было небольшое упоминание о решении таких проблем с помощью динамического программирования с битовыми масками, я не смог найти подробного объяснения этой техники.
PS: Хотя я знаю, как решить общую задачу разбиения сетки, скажем, в этой задаче, только если нам даны только пустые ячейки, тогда повторение может быть сформировано как F (n) = F (n-1) + F (n- 2), поместив костяшку 1x2 или две костяшки 2x1, чтобы закрыть первый и первые два столбца соответственно. Это можно решить итеративно или даже для больших N (скажем,> 10 ^ 7), мы можем использовать метод матричного возведения в степень. Но мне интересно узнать о технике решения подобных проблем с помощью DP+Bitmasks. Любая помощь будет оценена по достоинству.
