除数博弈
爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。
最初,黑板上有一个数字 n 。在每个玩家的回合,玩家需要执行以下操作:
选出任一 x,满足 0 < x < n且 n % x == 0。
用 n - x替换黑板上的数字 n。
如果玩家无法执行这些操作,就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 true。假设两个玩家都以最佳状态参与游戏。
示例 1:
输入:n = 2 输出:true 解释:爱丽丝选择 1,鲍勃无法进行操作。
示例 2:
输入:n = 3 输出:false 解释:爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。
我的思路:
这个题最开始看很复杂,感觉要用dp,用dp肯定看可以做出来,但是按分类的话,这个题应该是一个贪心题,也就是博弈论方面的题目,做这种题最重要的是什么:“找规律”,先不谈什么推到公式,就单纯的一个个的枚举n的前面的情况:
n == 1, false; n == 2, true; n == 3, false; n == 4, true; ....
然后发现好想见就是只要是偶数就是true,然后试试可不可以过,然后就过来,就这么简单。
我的代码:
class Solution { public: // 一个数学技巧题 bool divisorGame(int n) { return n % 2 == 0; } };