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

Я пытаюсь решить следующую проблему DP:

У вас есть 4 типа блоков lego, размеров 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 блоков с b c d , Допустимые шаблоны выделены жирным шрифтом. Недопустимые шаблоны, которые могут быть разбиты по вертикальной линии.

H = 1 и W = 3 #valid pattern = 1
aa ab ba c

H = 2 и W = 3 #valid pattern = 9

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

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

Ответ 1

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

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

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

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

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

Отделение в самом левом месте, где стена не подключена. Число стенок A l W * H - это количество стенок S olid X * H, умноженное на количество стенок A ll {W-X}*H, суммированных по всем возможным значениям X, плюс число S olid 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 (при условии правильной арифметики операций memoization и постоянной времени)

Ответ 2

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

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

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