建造2x1x1块的2 ^ N塔（基座面积2x2）有多少可能性？这必须是一个分而治之的算法，正如我目前所理解的我算出了O（2^n），但我想在多项式时间内解决这个问题。
我的主要问题是找出“征服”的部分。
有人能给我一个如何在多项式时间内解决这个问题的建议吗？
Example
最佳答案
设f（n）为从平底建造高度为n的塔的方法数，s（n）为从一半填充的底建造高度为n的塔的方法数。
然后f（n）=2f（n-1）+4s（n-1），s（n）=f（n-1）+s（n-1）。
这是因为如果你从一个平坦的底部开始，有两种方法可以完全填充底层，而不会有任何碎片向上突出，还有四种方法可以将一块放平，两块向上突出。同样地，如果你有一个半填充的底部，你可以通过添加一个平躺的部分来完成这个层，或者再添加两个竖立的部分，这一半填充上面的层。
然后，您可以将其表示为矩阵向量乘法（在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)
你可以用平方的幂运算来计算0（log n）时间内的矩阵幂。这给了你一个O（n）算法来寻找建造2^n高塔的方法。
另一种方法（分而治之）是计算建造高度为2^n的塔的方法，其中底层要么是完整的，要么是垂直填充一半，要么是水平填充一半。然后你可以通过计算将9个不同的半塔中的两个组合在一起的方法，每次将问题减半虽然计算起来比较复杂，但仍然是o（n），因为不能使用矩阵幂技巧，因为出现了一些平方项。
关于algorithm - 用2x1x1块的2x2基座构造2 ^ n高的塔的可能性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50896879/