乐高积木 - 动态规划

Question

我正在尝试解决以下DP问题:

您有4种类型的乐高积木,尺寸为1*1*1,1*1*2,1*1*3和1*1*4.假设您拥有无限数量的每种类型的积木.

你想在这些块中制作一个高度为H和宽度为M的墙.墙上不应有任何孔.你建造的墙应该是一个坚固的结构.坚固的结构意味着不应该沿着任何垂直线分开墙壁而不切割用于建造墙壁的任何乐高积木.块只能水平放置.墙可以建造多少种方式？

以下是我的尝试方法:用abcd表示1*1*1,1*1*2,1*1*3和1*1*4块.有效模式以粗体表示.无效模式可以被垂直线打破.

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

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

我试图通过高度或宽度来找到递推模式,以找到H = 3&W = 3或H = 2&W = 4的值.

关于如何通过身高或体重来计算增长的任何输入？
PS墙壁总是H*W*1.

Answer 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的答案已经包含了基本前提:

在没有连接墙的最左边的地方分支.数ALL W*H城墙是多少S奥利德X*H墙次数ALL {W-X}*H墙,穿过的所有可能值相加X,再加上数量S奥利德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(假设适当的记忆和恒定时间算术运算)

Answer 2

找到一些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)*A(H,WL)是非实心壁的数量,最左边的断裂位于L垂直位置.第一个因素是固体墙的数量 - 消除重复变体的计数.