Lego блоки - Динамическое программирование

Question

Я пытаюсь решить следующую задачу DP:

У вас есть 4 типа лего блоков, размеров 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3 и 1 * 1 * 4. Предположим, что у вас есть бесконечное количество блоков каждого типа.

Вы хотите сделать стену высотой H и шириной M из этих блоков. На стене не должно быть отверстий. Стена, которую вы строите, должна быть одной сплошной структурой. Твердая структура означает, что не должно быть можно отделить стену вдоль любой вертикальной линии без резки любой блок lego, используемый для сборки стены. Блоки могут размещаться только по горизонтали . Сколько способов построить стену?

Вот как я пытаюсь это: Представляя 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3 и 1 * 1 * 4 блоки с A B C D . Допустимые шаблоны выделены жирным шрифтом. Недопустимые шаблоны, которые могут быть разбиты по вертикальной линии.

Н = 1 & W = 3 #valid узор = 1
аа аб ба с

Н = 2 & W = 3 #valid узор = 9

Я пытаюсь найти шаблон повторения, чтобы увеличить его по высоте или ширине. Найти значения для H = 3 & W = 3 или H = 2 & W = 4.

Любые входные данные о том, как увеличить формулу для роста по высоте или весу?
P.S. Стена всегда H * W * 1.

Answer 1

Нетрудно найти несколько полосок 1xW (пусть это N (1, W)). Затем вы можете найти ряд всех (в том числе не сплошных) стен HxW - это A (H, W) = N (1, W)^H Любая сплошная стена состоит из левой стены H * L и правой H * (WL). Кажется, что количество твердых стенок

S(H,W) = A(H,W) - Sum(S(H, L) * A(H, W-L)) [L=1..W-1]

S (H, L) * А (Н, W-L) количество нетвердых стен с крайним левым перерывом в L вертикального положения. Первым фактором является количество сплошных стен - исключить подсчет повторяющихся вариантов.

Answer 2

Во-первых, давайте посмотрим, сколько M * N стены можно построить, если мы пренебрегаем необходимость держать их подключившиеся:

Мы можем рассматривать каждую строку отдельно, а затем умножить счетчики, так как они являются независимыми.

Существует только один способ плитку 0*1 или 1*1 стены, и количество способов плитки n*1 является суммой количества способов плитки {n-1}*1 ... {n-4}*1 -sized стены, причина в том, эти стены можно получить, удалив последнюю плиту стены n*1.

Это приводит к последовательности тетранацци, OEIS A000078. Количество всех W*H стен a(w,h)=T(w)^h.

Теперь, чтобы подсчитать количество сплошных стен. Ответ МБО уже содержит основную посылку:

Отделение в самом левом месте, где стена не подключена. Количество A LL W * H стена этого число S Olid X * H стена, умноженные на числе A LL {W-X}*H стена, просуммировать по всем возможным значениям X, плюс число S õlid W * H стена:

A(W,H) = sum{X=1..{W-1}}(S(X,H)*A(W-X,H)) + S(W,H) 

в качестве последнего шага, мы выделим S(M,H) термин, который является значением, которое мы хотим вычислить, и повторить предыдущие формулы:

S(W,H) = A(W,H) - sum_x(S(X,H)*A(W-X,H)) //implicitly, S(1,H)=1 

A(W,H) = T(W)^H 

T(X) = X > 0: T(X-1)+T(X-2)+T(X-3)+T(X-4) 
     X = 0: 1 
     X < 0: 0 

(доказав формула MBO Правильна).

Это также обеспечивает O(W^2) алгоритм вычисления S (при условии надлежащей мемоизации и постоянная время арифметических операций)