c++ - 为什么我们在填充计数图块时可以使用单个框替换水平和底部垂直片段？

Question

这里我们有一个 4 * 7 的盒子，它可以用 1 * 2 或 2 * 1 的矩形填充。这个描述来自《竞争程序员手册》一书。

为了最有效地解决这个问题，书中提到使用可以在特定行中的部分：

由于这个集合中有 4 个东西，我们可以拥有的最大唯一行是 4^m，其中 m 是列数。从每个构造的行中，我们构造下一行以使其有效。有效意味着我们不能有乱序的垂直片段。只有当顶行中的所有垂直“caps”都对应于底行中的垂直“cups”并且反之亦然时，该解决方案才有效。（显然对于水平片段，它们的构造受限于行创建本身，因此这里不可能存在行间差异。）

这本书然后神秘地说：

通过对行使用更紧凑的表示，可以使解决方案更有效。事实证明，知道前一行的哪些列包含垂直瓦片的上部正方形就足够了。因此，我们可以仅使用垂直瓦片的上方块字符和□来表示一行，其中□是字符下垂直方块、左水平方块和右水平方块的组合。使用这种表示，只有 2^m 不同的行，时间复杂度为 O(n2^(2m))。

为什么这个简单的正方形会起作用？你怎么知道顶部垂直片段下方是否有一个水平框？你怎么知道左右水平片段是对齐的？它打破了我的想法，为什么这是可能的。有人知道吗？

这是我对 2 x n 矩阵的特别 C++ 实现，在这种情况下不起作用，但我试图将其抽象：

int ways[251];

int f(int n){
    if (ways[n] != 1) return ways[n];
    return (ways[n] = f(n-1) + f(n-2));
}

int main(){
    ways[0] = 1;
    ways[1] = 1;
    for (int i = 2; i <= 250; i++){
        ways[i] = -1;
        cout << f(250) << '\n';
    }
}

标签： c++dynamic-programming