为什么这个问题的时间复杂度只考虑了前面的递归调用，而不考虑整个问题？

问：

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

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

由于该集合中有 4 个内容，因此我们可以拥有的最大唯一行数为 4^m，其中 m 是列数。从每个构造的行中，我们构造下一行，使其有效。有效意味着我们不能让垂直片段乱序排列。只有当顶行中的所有垂直“大写字母”都与底行中的垂直“杯子”相对应时，反之亦然，解决方案才有效。（显然，对于水平片段，它们的构造在行创建本身中受到限制，因此此处不可能存在行间差异。

然后，这本书是这样说的：

由于一行由 m 个字符组成，并且有四个选项 每个字符，不同行数最多为 4^m。因此， 解的时间复杂度为 O（n4^{2m}），因为我们可以通过 每行的 O（4^m） 可能状态，对于每个状态，有 O（4^m） 上一行的可能状态。

一切都很好，直到最后一句话，“前一行有 O（4^m） 种可能的状态。为什么我们只考虑前一行？有更多的行，这一次复杂度应该考虑整个问题，而不仅仅是前一行，对吧？

这是我对 n 矩阵 2 的临时 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';
    }
}