language-agnostic - 有没有人见过类似的编程难题？

Question

“假设你想用一排排 4×1 和 6×1 的乐高积木搭建一个实心面板。为了结构强度，积木之间的空间绝不能在相邻的行中排列。例如，所示的 18×3 面板下面是 Not Acceptable ，因为顶部两行中的块之间的空间对齐。

10×1面板有2种方式，10×2面板有2种方式，18×3面板有8种方式，36×5面板有7958种方式。

有多少种不同的方法来构建 64×10 面板？答案将适合 64 位有符号整数。编写一个程序来计算答案。您的程序应该运行得非常快——当然，即使在较旧的机器上，它也不应该超过一分钟。让我们知道您的程序计算的值、您的程序计算该值所需的时间以及您在何种机器上运行它。包括程序的源代码作为附件。
”

我最近收到了一个编程难题，并一直在绞尽脑汁试图解决它。我使用 c++ 编写了一些代码，我知道这个数字很大……我的程序运行了几个小时，然后我决定停止它，因为即使在慢速计算机上也需要 1 分钟的运行时间。有没有人见过类似的拼图？已经几个星期了，我不能再提交这个了，但这真的让我烦恼，我无法正确解决它。关于使用算法的任何建议？或者也许可能的解决方法是“开箱即用”。我采用的是制作一个程序，该程序构建了 4x1 和 6x1 块的每个可能的“层”以制作 64x1 层。结果证明大约有 3300 个不同的层。然后我让我的程序运行并将它们堆叠成所有可能的 10 层高的墙壁，这些墙壁没有排列的裂缝……正如你所看到的，这个解决方案需要很长很长很长的时间。所以很明显，在时间限制内，蛮力似乎并不能有效地解决这个问题。任何建议/见解将不胜感激。

Answer 1

主要见解是:在确定第 3 行中的内容时，您不关心第 1 行中的内容，只关心第 2 行中的内容。

因此，让我们将如何构建 64x1 层称为“行场景”。你说大约有3300行场景。那还不错。

让我们计算一个函数:

f(s, r) = 将行场景编号“s”放入“r”行并合法填充“r”上方的所有行的方法数。

(我在顶部的“1”行和底部的“10”行进行计数)

如果您想避免剧透，请立即停止阅读。

现在很清楚(将我们的行从 1 编号到 10):

f(s, 1) = 1

对于“s”的所有值。

此外，这就是洞察力的来源，(使用 Mathematica 符号)

f(s, r) = Sum[ f(i, r-1) * fits(s, i) , {i, 1, 3328} ]

其中“fits”是一个函数，它接受两个场景编号，如果您可以合法地将这两行堆叠在一起，则返回“1”，如果不能，则返回“0”。这使用了洞察力，因为放置场景的合法方式的数量仅取决于根据“适合”将场景放置在其上方的方式的数量。

现在，可以预先计算拟合并将其存储在 3328 x 3328 字节数组中。那只有大约 10 兆的内存。 (如果您喜欢并将其存储为位数组，则更少)

那么答案显然是

Sum[ f(i, 10) , {i, 1, 3328} ]