17

我正在尝试解决以下 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 #有效模式=1
aa ab ba c

H=2 & W=3 #有效模式=9
在此处输入图像描述

我试图找到重复模式以通过高度或宽度扩展它。即找到 H=3 & W=3 或 H=2&W=4 的值。

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

4

2 回答 2

12

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

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

只有一种方法可以平铺 a0*1或1*1墙壁，并且平铺 an 的方式的数量是平铺...大小墙壁n*1的方式的总数，原因是这些墙可以通过移除最后一个瓷砖来获得的墙。{n-1}*1{n-4}*1n*1

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

现在，计算实心墙的数量。MBo 的回答已经包含了基本前提：

在最左边没有连接墙壁的地方分支。All W*H 墙的数量是原始SX*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（假设适当的记忆和恒定时间算术运算）

于 2013-03-15T06:33:07.707 回答
9

不难找到多个 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 垂直位置最左边的非实心墙的数量。第一个因素是实体墙的数量 - 消除重复变体的计数。

于 2013-03-15T05:20:40.437 回答