algorithm - 可以建造 2^n 高的塔，2x2 基地的 2x1x1 块

Question

建造 2x1x1 块的 2^n 塔（基地面积 2x2）有多少种可能性？正如我目前所理解的那样，这必须是一种分而治之的算法。我想出了O(2^n)，但我想在多项式时间内解决这个问题。

我的主要问题是找出“征服”部分。

有人可以给我一个建议如何在多项式时间内解决这个问题吗？

例子

标签： algorithmsortingpermutationtiling

Answer 1

令 F(n) 是从平底建造高度为 n 的塔的方法数，而 S(n) 是从填充一半的基础建造高度为 n 的塔的方法数。

那么 F(n) = 2F(n-1) + 4S(n-1)，并且 S(n) = F(n-1) + S(n-1)。

那是因为如果你从一个扁平的底座开始，有两种方法可以完全填充底层而不会有任何碎片突出，还有 4 种方法可以放下一块平整，两块向上。同样，如果你有一个半填充的底座，你可以通过添加一个平躺的部分来完成该层，或者添加另外两个粘贴的部分，其中一半填充上面的层。

然后，您可以将其表示为矩阵向量乘法（在 ASCII 艺术中）：

F(n) = (2 4) (F(n-1))
S(n) = (1 1) (S(n-1))

所以：

F(n) = (2 4)^n (F(0))
S(n) = (1 1)   (S(0))

由于 F(0) = 1 和 S(0) = 0，你有：

F(n) = (2 4)^n (1)
S(n) = (1 1)   (0)

您可以使用通过平方取幂来计算 O(log n) 时间内的矩阵幂。这为您提供了一个 O(n) 算法来寻找建造 2^n 高度塔的方法。

一种不同的（分而治之）方法是计算建造高度为 2^n 的塔的方式，其中底层要么是完整的，要么是垂直填充的一半，或者是水平填充的一半。然后，您可以通过计算将 9 个不同半塔中的两个组合在一起的方法，每次都将问题减半。但是，计算起来更复杂，而且仍然是 O(n)，因为您不能使用矩阵幂技巧，因为出现了一些平方项。