1025、除数博弈
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 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
题解
1、找规律，数学归纳法证明
博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：
- N = 1 的时候，区间 (0, 1)(0,1) 中没有整数是 nn 的因数，所以此时 Alice 败。
- N = 2 的时候，Alice 只能拿 11，NN 变成 11，Bob 无法继续操作，故 Alice 胜。
- N = 3 的时候，Alice 只能拿 11，NN 变成 22，根据 N = 2N=2 的结论，我们知道此时 Bob 会获胜，- Alice 败。
- N = 4 的时候，Alice 能拿 11 或 22，如果 Alice 拿 11，根据 N = 3N=3 的结论，Bob 会失败，- Alice 会获胜。
- N = 5 的时候，Alice 只能拿 11，根据 N = 4N=4 的结论，Alice 会失败。
- …
class Solution{
public boolean divisorGame(int N) {
return N % 2 == 0;
}
}
2、递推
class Solution {
public boolean divisorGame(int N) {
boolean[] f = new boolean[N + 5];
f[1] = false;
f[2] = true;
for (int i = 3; i <= N; ++i) {
for (int j = 1; j < i; ++j) {
if ((i % j) == 0 && !f[i - j]) {
f[i] = true;
break;
}
}
}
return f[N];
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
