本文共 1258 字，大约阅读时间需要 4 分钟。

爱丽丝和鲍勃玩一个数论游戏，规则是将一个数n分解成两个因数，爱丽丝先拿较大的因数，鲍勃随后拿较小的因数。爱丽丝的目标是通过减少自己的数字让最终数字减到1，而鲍勃则希望做到同样的事情，且两位玩家都不会让对方拿到0。我们需要判断给定数字n下，爱丽丝是否有必胜策略。

方法一：逻辑分析

这里有一个巧妙的观察点，所有的胜负都取决于n是奇数还是偶数。

因此，胜负的决定因素非常简单：仅需判断n的奇偶性。

class Solution {public:    bool divisorGame(int n) {        return !(n % 2);    }}

方法二：动态规划

另一个方法是使用动态规划来记录每个数值i的状态，爱丽丝在i处能否必胜。我们用dp数组记录爱丽丝拿到数字i时的状态，true表示她可以必胜，false表示不行。

class Solution {public:    bool divisorGame(int n) {        vector
   
     dp(n + 1, false);        if (n <= 2) {            return n == 2; // 初始化，爱丽丝拿到1输，拿到2赢        }        dp[2] = true;        for (int i = 3; i <= n; ++i) {            for (int j = 1; j < i; ++j) {                if (i % j == 0 && !dp[i - j]) {                    dp[i] = true;                    break;                }            }        }        return dp[n];    }}
   

通过这两种方法，我们可以轻松判断爱丽丝是否在给定的数字n下有必胜策略，关键点在于n的奇偶性决定了胜负。而动态规划方法则为更复杂的数论问题提供了解决方案。