今天看到某公司的一道笔试题，是经典的斐波那契Nim游戏：

问题

A 和 B 轮流取数，一共有 个物品，A 是先手，先手第一次可以取个物品。每个人每次最少取1个物品，最多取前一个人取的数量的2倍，先取完者胜。假设双方都采取最优策略，问A是否能赢得游戏。

动态规划

这是一个典型的动态规划问题。游戏中可能出现的状态为，其中为当前剩下的物品，为最多可取的物品数量。假设表示游戏的结果（0=输，1=赢），那么问题相当于求解。

按照题意，要赢得比赛，必须有一种取物品的方法，使得取完后的状态必然会输掉比赛。也就是说，的充分必要条件，是存在使得。

此外，如果, 必然有，这是显然的。因此如果，必然有从而。

根据以上分析，我们可以写出如下的动态规划算法：

vector<vector<bool>> f(N + 1, vector<bool>(N + 1, false));
for (int n = 1; n <= N; n++) {
    for (int k = 1; k < n; k++) {
        bool if_win = false;
        for (int i = 1; i <= k && 3 * i < n && !if_win; i++) {
            if (f[n - i][2 * i] == 0) if_win = true;
        }
        f[n][k] = if_win;
    }
}
cout << (f[N][N - 1] ? "win" : "lose") << endl;

可以看到上面的算法复杂度是，在大部分机考中只能AC几百这个量级的数据。这篇文章主要讨论的是如何进一步降低算法的复杂度。降低算法复杂度的关键在于挖掘动态规划中各个变量的关键性质，并加以运用。

优化

首先，我们注意到，如果，那么必然有。这是因为k表示的是最大可以选取的物品数量，那么如果在状态下可以获胜，在下当然也可以获胜。根据这个性质，我们可以改变我们的动态规划目标，用更高效的方法保存，使得状态数大大减少。我们用表示最小的使得成立的。

下面来看看如何求。的特殊情形可以在的时间内判定，因为这等价于。下面考虑的一般情形。

如果，那么必然有
也就是说，最多取个物品时赢，最多取个物品时输。这显然表明，取个物品会赢，而取任何比少的物品时就会输。这表明是最小的使得成立的。

但是我们的动态规划变量里只有，已经没有了，不能用来求。怎么办呢？这时候就要注意到,根据我们对的定义，

因此，我们的状态转移方程就变成了

我们可以设置一个初始条件，因为当物品只剩下0个时，已经输掉了比赛。这样就可以写出下面的动态规划算法（优化1）

vector<int> g(N + 1, INT_MAX);
for (int n = 1; n <= N; n++) {
    for (int k = 1; k <= n; k++) {
        if (g[n - k] > 2 * k) {
            g[n] = k; break;
        }
    }
}
cout << (g[N] < N ? "win" : "lose") << endl;

可以看到上面算法的复杂度为。这样我们的算法就能够AC几千这个量级的数据了。

进一步优化

并不理想。我们的目标是线性复杂度，这样可以AC几十万到几百万这个量级的数据。为了做到这一点，我们需要深入挖掘状态转移方程的规律。

我们来看看到底是什么。在求解的过程中，我们其实考察了以下的数列

我们相当于在寻找第一项取+号的元素。那么我们再来看看求解的时候会发生什么。在求时，我们考察的数列是

注意到了什么？从的数列到的数列，每项元素都减少了2。（同时新增了一项，但这不是重点）也就是说，如果在的数列中某一项是负数，那么在的数列它还是负数：我们根本就不需要检查这些元素。

形式化的证明如下。我们的状态转移方程可以改写成

对于动态规划数组中某一项，假设在求解时发现，从而跳过了这一项，那么在求解时，也一定会有，从而跳过这一项。因此，我们可以采用一个容器，记录所有可能成为中元素的值。如果在求解时发现某个元素不满足条件，我们可以将弹出，使得后续不再考虑。每次在计算完后，我们要将也加入这个容器。由于我们要求的是最大的，我们可以选取单调栈作为我们的容器数据结构。这使得我们可以在的时间内访问最大元素、弹出栈顶和加入新元素（注意到我们加入的新元素一定是最大元素，因此不需要使用优先队列等更慢的数据结构）。

vector<int> g(N + 1, INT_MAX);
stack<int> stk;
stk.push(0);
for (int n = 1; n <= N; n++) {
    while (g[stk.top()] <= 2 * (n - stk.top())) stk.pop();
    g[n] = n - stk.top();
    stk.push(n);
}
cout << (g[N] < N ? "win" : "lose") << endl;

可以看到每次执行一次while循环都有一个元素出栈。但总共只有个元素进栈，因此第5行的总体时间复杂度是。代码其他部分的时间复杂度显然也是，因此算法时间复杂度为。

写在最后

其实这个问题存在复杂度更低的算法：。通过实验可以发现，当且仅当为斐波那契数列中的元素时，才会输掉比赛。我们可以很容易在时间内判断某个数是不是斐波那契数列中的元素。

int prev = 0, cur = 1, tmp;
bool if_win = true;
while (cur <= N && if_win) {
    if (prev + cur == N)  if_win = false;
    tmp = cur, cur = prev + cur, prev = tmp;
}
cout << (if_win ? "win" : "lose") << endl;

但是这是个很深刻的数学结论，因此在算法题中不会考察。有兴趣的同学可以参考Fibonacci Nim相关的文章。
https://math.stackexchange.com/questions/2762700/proof-of-winning-strategy-in-fibonacci-nim