每日一题之除数博弈

题目1025：除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

• 选出任一 x，满足 0 < x < N 且 N % x == 0 。

• 用 N - x 替换黑板上的数字 N 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

示例1：

输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例2：

输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

提示：

1. 1 <= N <= 1000

分析

动态规划问题，当前玩家在某个数字的成功失败与否可以由更小的数字成功与否推断出来，使用false_idx[]存储会失败的数字，1和3会失败，先把数字1和3存储在false_idx中，顺序将i从4遍历到N，对i的处理过程中，如果当前玩家可以选择一个数字x，这个数字满足i % x == 0，并且i - x在false_idx数组中，证明下个玩家一定会失败，那当前玩家就一定会成功，根据当前玩家在当前数字成功失败与否来更新false_idx数组。这道题还有数学方法奇偶性可以解，这里主要介绍动态规划思路，数学方法有兴趣大家可以自行搜索研究。

代码

class Solution {
public:
    bool divisorGame(int N) {
        if (N == 1 || N == 3) {
            return false;
        }
        if (N == 2) {
            return true;
        }
        vector<int> false_indexs;
        false_indexs.push_back(1);
        false_indexs.push_back(3);
        for (int i = 4; i <= N; ++i) {
            bool is_win = false;
            for (auto idx : false_indexs) {
                if (i % (i-idx) == 0) {
                    is_win = true;
                    break;
                }
            }
            if (!is_win) {
                false_indexs.push_back(i);
            }
        }
        return false_indexs.back() != N;
    }
};

更多文章请关注

programmer