【LeetCode】1025 除数博弈

发表于 | 分类于

1. 题目描述

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

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

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。

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

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

示例 1：

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

示例 2：

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

提示：

1 <= N <= 1000

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/divisor-game 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/divisor-game

2. 动态规划法

乍一看，这不就是巴什博弈么？仔细观察才发现还是有些不同的，巴什博弈中对于取石子的数量没有约束，而这里要求必须是整除。

由于这道题是我在动态规划专题里看到的，所以第一反应就是怎么使用动规。试过以后才发现动态规化还挺合适这一类博弈问题的(当然，并非最优解答)。

首先来总结一下这一类博弈问题的基本特点吧。

  1. 可以用某个整数值来表征当前的局面；例如 n = 10 表示黑板上的数字是 10
  2. 固定的局面对应了固定的结果，且上下文无关；例如 n = 10 的时候先手必败，那就意味着不管是一开始就是 10 还是从其他局面转移到当前局面，处身于当前局面的先手必败（即具有了状态转移的特性）
  3. 各个局面之间具有很强烈的序列关系

所以，这种类型的博弈问题都可以用这样的搜索结构来解决:

1
2
3
4
5
6
7
8
9
for 局面 i = 1:n
    for each action
        i --action--> j，且 j < i
        if 局面 j 对先手而言是必败局
            局面 i 对先手是必胜局
            break
    else
        不管做什么动作，都会变成对于对手而言的必胜局
        所以 i 对先手是必败局

有了这样的分析，我们就有了 AC 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
    bool divisorGame(const int N)
    {
        bool alice[N + 1];
        alice[1] = false;
        bool ans;
        for (int i = 2; i <= N; ++i)
        {
            ans = false;
            //遍历所有合法的动作
            for (int x = 1; x < i; ++x)
            {
                //如果有一个 x 能够使得对方陷入 false 的境遇，那么当前的状况就是 true 的
                if (i % x == 0)
                {
                    if (alice[i - x] == false)
                    {
                        ans = true;
                        break;
                    }
                }
            }
            alice[i] = ans;
        }
        return alice[N];
    }
};

3. 归纳总结法

我们说了，上面的动态规划方法并不是最优的解。这种博弈问题一般经过严密的数学分析后都可以变得及其简单。

首先模拟一下:

游戏开始时，
假设N=1，爱丽丝失败；
假设N=2，她可以选择x=1，来使鲍勃遇到的N=2-1=1，无法操作，爱丽丝获胜；
假设N=3，她只能选择x=1，鲍勃遇到的N=2，鲍勃获胜；
假设N=4，她可以选择x=1，来使鲍勃遇到的N=3，爱丽丝获胜；
······

我们

  1. 注意到 N = 2 是一个必胜局面。
  2. 奇数的因子只能是奇数，偶数的因子可以是奇数或偶数。

所以:

  • N 是偶数时，总可以选到一个 N 的奇数因子 x（比如1）， 使得传给对方的 N-x 为奇数，而对方遇到奇数 N，只能选择 N 的奇数因子 x， 又会将偶数的 N-x 传回给爱丽丝，最终爱丽丝会遇到 N = 2，然后获胜。
  • N 是奇数时，只能传给对方偶数或无法操作 (N = 1)，无法获胜。
1
2
3
4
5
6
7
8
class Solution
{
public:
    bool divisorGame(int N)
    {
        return N % 2 == 0;
    }
};