爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作： 选出任一 x，满足 0 < x < N 且 N % x == 0 。 用 N - x 替换黑板上的数字 N 。 如果玩家无法执行这些操作，就会输掉游戏。 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏
方法一： 找规律的解答方式： 针对于博弈类的问题，我们尝试几项看看规律所在。 N = 1 的时候，区间 (0,1) 中没有整数是 n 的因数，所以此时 Alice 败。 N = 2 的时候，Alice 只能拿 1，N 变成 1，Bob 无法继续操作，故 Alice 胜。 N = 3 的时候，Alice 只能拿 1，N 变成 2，根据 N=2 的结论，我们知道此时 Bob 会获胜，Alice 败。 N = 4 的时候，Alice 能拿 1 或 2，如果 Alice 拿 1，根据 N=3 的结论，Bob 会失败，Alice 会获胜。 N = 5 的时候，Alice 只能拿 1，根据 N=4 的结论，Alice 会失败。
上述几项总结出的规律：N 为奇数时Alice(先手)必败，N为偶数的时候Alice必胜。
发现规律的证明 上述规律的证明： 1.N = 1 和N = 2 时结论成立。 2.N > 2 时，假设 N ≤ k 时该结论成立，则 N=k+1 时： 1）如果 k 为偶数，则 k+1为奇数，x是 k+1的因数，则x只可能是奇数，而奇数减去奇数等于偶数，且 k + 1 - x ≤ k， 故轮到Bob都会是偶数。由上面的结果可以知道只要是先手拿到偶数就是必胜，所以此时Alice必败。 2）如果 k 为奇数，k+1为偶数，x 可以是奇数也可以是偶数，因为他们都处于游戏的最佳状态，所以Alice肯定会选择是减去一个奇数，那么 k + 1 - x 的结果是 ≤ k的奇数 ，因为此时轮到Bob,所以Bob属于必败状态，Alice属于必胜。
代码:
代码说明： 上述只要N是偶数，对应的k就是奇数，则返回的判断结果就是True; 若N的结果是奇数，则对应的kj就是偶数，则返回的结果就是 false。
定义 f[ i ]表示当前数字i的时候先手处于必胜还是必败，true表示先手必胜，false表示先手必败，所以代码需要满足的是，枚举 i 在（0，i）中 i 的因数j,看是否存在f[i−j] 为必败态即可，说明 f[i] 即为必胜状态。
代码：
package dongtaiguihua.demo; //力扣题集1025 除数博弈 class Solution { public boolean divisorGame(int N){ boolean[] f = new boolean[N+5]; f[1] = false; //表示先手必败 f[2] = true; //先手必胜 // f数组中未赋初值的情况，初始值均为false //这里是从前往后推这样做的目的是，我们要求得目标结果是f[N],但是这里从头开始遍历就可以求出 //小于N 数的情况的f[]的值，然后将其记录存储在数组中，后面遍历的时候直接使用已经存储的结果就好， //这也是动态规划的核心思想 for( int i = 3; i <= N; i++ ){ for( int j = 1; j < i; j++){ //这里判断的条件的意思是当前值j能否被i整除，同时f[i-j]是否false //如果同时满足上面两个条件，则说明当前的i值得f[i]处于必胜状态 if((i % j) == 0 && !f[i-j]){ f[i] = true; } } } //经过多次循环后得到的最终结果f[N] return f[N]; } public static void main(String[] args){ int N = 4; Solution dcs = new Solution(); dcs.divisorGame(N); } }