Эта задача можно решить с помощью динамического программирования.
Пусть dp[N] – количество способов замостить полосу размера 2× N
Шаги решения:
1. Инициализируем массив dp[N] нулями.
2. Задаем базовые случаи: dp[0] = 1 (если полоса пуста, то способов замостить ее тоже 1) и dp[1] = 1 (если полоса имеет размер 2×1, то есть только один способ ее замостить).
3. Далее, рассматриваем каждую клетку полосы и заполняем массив dp[N] по формуле:
dp[N] = dp[N – 1] + dp[N – 2], где N > 1
На каждом шаге рассматриваем два предыдущих варианта: либо последняя клетка замощена горизонтальной доминошкой, либо вертикальной доминошкой.
4. После того как все клетки полосы были рассмотрены, в dp[N] будет содержаться искомое количество способов замостить полосу размера 2× N.
5. Возвращаем dp[N] в качестве ответа.
Объяснение:
Начиная с пустой полосы, мы можем добавлять горизонтальные или вертикальные доминошки, чтобы замостить ее. Если мы добавляем горизонтальную доминошку, то следующую доминошку мы тоже можем добавить горизонтально или вертикально. Если мы добавляем вертикальную доминошку, то следующую доминошку мы также можем добавить горизонтально или вертикально.
По этой логике, мы можем рассмотреть все возможные комбинации размещения доминошек на полосе размера 2× N и посчитать количество способов.