algorithm - 乐高积木 - 动态规划

Question

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

You have 4 types of lego blocks, of sizes 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3 and 1 * 1 * 4. Assume you have infinite number of blocks of each type.

You want to make a wall of height H and width M out of these blocks. The wall should not have any holes in it. The wall you build should be one solid structure. A solid structure means that it should not be possible to separate the wall along any vertical line without cutting any lego block used to build the wall. The blocks can only be placed horizontally. In how many ways can the wall be built?

这是我尝试的方式: 用a b c d表示1 * 1 * 1、1 * 1 * 2、1 * 1 * 3和1 * 1 * 4 block .有效模式以粗体表示。无效模式可以用垂直线分隔。

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 的值。

关于如何通过高度或体重公式化增长的任何输入？
附言墙总是 H*W*1。

Answer 1

首先，让我们看看如果忽略保持它们连接的需要，我们可以 build 多少 M*N 堵墙:

我们可以分别处理每一行，然后将计数相乘，因为它们是独立的。

只有一种方法可以平铺 0*1 或 1*1 墙，而平铺 n*1< 的方法有多种 是平铺 {n-1}*1...{n-4}*1 大小的墙的方法总数，原因这些墙可以通过移除 n*1 墙的最后一 block 瓷砖来获得。

这产生了一个 tetranacci 序列，OEIS A000078 . 所有 W*H 墙的数量是 a(w,h)=T(w)^h。

现在，来统计实体墙的数量。MBo的回答已经包含了基本前提:

最左边没有连接墙的地方的分支。 All W*H 墙的数量是 Solid X*H 墙的数量乘以 All { W-X}*H 墙，X 的所有可能值的总和，加上 Solid 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(假设适当的内存和恒定时间算术运算)