小旭讲解 LeetCode 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/

小旭讲解 LeetCode 1025. 除数博弈leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 1025. 除数博弈leetcode刷题题解