小旭讲解 1025. 除数博弈
文章目录


原题

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

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

选出任一 x,满足 0 < x < N 且 N % x == 0 。
用 N – x 替换黑板上的数字 N 。
如果玩家无法执行这些操作,就会输掉游戏。

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

示例 1:

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


示例 2:

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

思路 – 动态规划

玩家在每次博弈时的到的数字是 N,假设选择的数字是 i,那么至多有1 ~ N – 1种选择,当然要去除 N % i != 0的情况。在每一种选择下,对手的数字即为 N – i。所以,我们可以枚举所有情况,来判定对手若有输的情况,我们即可赢;否则,输。

可以利用线性动态规划的方式来解决。

状态空间表达 dp[i] 表示当前选择获得数字 i

状态空间含义:dp[i] 的值代表能否获得胜利

状态空间计算:两维的循环递推计算即可

代码

class Solution {
public:
    bool divisorGame(int N) {
        bool dp[N + 1];
        memset(dp, false, sizeof dp);
        for (int i = 2; i <= N; ++i) {
            for (int j = 1; j < i; ++j) {
                if (i % j != 0) continue;
                if (dp[i - j] == false) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N];
    }
};

复杂度分析

时间复杂度:O(N^2)
空间复杂度:O(N)

思路 – 归纳法

通过试算几项可以看出,奇数时 Alice 败,偶数时 Alice 胜利。

证明

  1. 当 N = 1 / 2 时 结论成立
  2. 当 N > 2 时
    1. 当 N 为奇数时,那么奇数的约数只有 1 和本身,所以下一个给对方留下的数字一定是偶数
    2. 当 N 为偶数时,偶数的约数可以是奇数也可以是偶数,若N被一个偶数减掉的话,那么给对方留下的数字即为奇数
  3. 所以,若Alice开始拿到的数字是偶数即胜利,奇数则失败
class Solution {
public:
    bool divisorGame(int N) {
        return N % 2 == 0;
    }
};

[1]. LeetCode 原题. https://leetcode-cn.com/problems/divisor-game/

本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-1025-divisor-game/
最后修改日期:2020年7月24日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。