Возможность построить башню высотой 2^n с основанием 2x2 из блоков 2x1x1

Question

Сколько существует возможностей построить башню 2^n (с базовой площадью 2x2) из ​​блоков 2x1x1? Как я понял, это должен быть алгоритм "разделяй и властвуй". Я разобрался с O (2^n), но я хотел бы решить эту проблему за полиномиальное время.

Основная проблема в моем случае - выяснить, как победить.

Может ли кто-нибудь дать мне совет, как решить эту проблему за полиномиальное время?

пример

Answer 1

Пусть F(n) - количество способов построения башни высотой n из плоского основания, а S(n) - количество способов построения башни высотой n из основания, где заполнена половина.

Тогда F(n) = 2F(n-1) + 4S(n-1) и S(n) = F(n-1) + S(n-1).

Это потому, что если вы начнете с плоской основы, есть два способа полностью заполнить нижний слой без каких-либо выступов, и есть 4 способа положить кусок плоско, с двумя торчащими вверх кусками. И точно так же, если у вас есть наполовину заполненная основа, вы можете либо завершить слой, добавив лежащий кусок, либо добавить еще две прилипающие части, которые наполовину заполняют слой выше.

Затем вы можете выразить это как умножение матрицы на вектор (в искусстве ASCII):

F(n) = (2 4) (F(n-1))
S(n) = (1 1) (S(n-1))

так что:

F(n) = (2 4)^n (F(0))
S(n) = (1 1)   (S(0))

Поскольку F(0) = 1 и S(0) = 0, у вас есть:

F(n) = (2 4)^n (1)
S(n) = (1 1)   (0)

Вы можете вычислить мощность матрицы за O(log n), используя возведение в степень путем возведения в квадрат. Это дает вам алгоритм O(n) для нахождения способов построения башни высотой 2^n.

Другой (разделяй и властвуй) подход заключается в подсчете способов построения башни высотой 2^n, где нижний слой либо заполнен либо наполовину заполнен по вертикали, либо наполовину заполнен по горизонтали. Затем вы можете вдвое сократить задачу, посчитав, как можно объединить две из 9 разных полу-башен вместе. Хотя работать сложнее, и все равно O(n), так как вы не можете использовать трюк мощности матрицы, потому что появляются некоторые квадратные термины.