Leetcode初学——动态规划算法“除数博弈”（假 ）

题目

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

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

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

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

示例 1：

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

输入：3
输出：false
题解

这道题真的很有意思，可以说是我目前遇到过的最有意思的题了，虽然它被打上了动态规划的标签，我觉得它其实就是一个脑筋急转弯，题目字面意思很容易理解，找除本身外的因数，找不到就输了。但是它实际做起来其实我觉的是比较的有难度的，通常做动态规划题的思路一般是从小的开始一点点扩大找规律，但是本题不同，本题类似于下棋，每个人其实都有不同的解法，同一个题目不同的解法很有可能就得出不同的结果，打个比方，当N=25时（A为爱丽丝，B为鲍勃）：

可以看出，最后爱丽丝无路可走失败了，但是换一种走法：

Leetcode初学——动态规划算法“除数博弈”（假 ）

原文：https://www.cnblogs.com/feite/p/13192466.html