题目
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。 用 N - x 替换黑板上的数字 N 。 如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。
题干
选出x比N小并且可以被x整除
再把N-x作为开局
都以最佳状态参与游戏- 即 每次选择都是以对自己最有利的进行
思路
数学逻辑
首页从逻辑角度来看 每个玩家如何保证自己赢面最大
涉及到整除 就有奇数和偶数之分
如果N为奇数 只有奇数可以整除奇数 奇数-奇数=偶数 那么给下一个玩家的数必为偶数
如果N为偶数 能被偶数整除 也能被奇数整除
如果选了偶数 偶数-偶数必为偶数 那么给下一个玩家的数必为偶数
如果选了奇数 偶数-奇数必为奇数 那么给下一个玩家的数必为奇数
那到底选哪种才是最有利的 我们来想想最终什么情况会输掉游戏
已知N为递减的 会无限趋向为1 当有一方拿到1时另一方无法做下去 拿到1的一方获胜
那如何拿到1呢 根据我们上面的推论 接收到的为奇数方有可能拿到同为奇数的1
所以爱丽丝如果是偶数开局 选取奇数 让鲍勃只能给它返回偶数 就能保证这个偶数无限趋向于2
再选择1爱丽丝就可以稳操胜券
如果爱丽丝是奇数开局 那么就不太妙了 它只能返回偶数给鲍勃 鲍勃同样可以利用这个规律
只返回奇数给爱丽丝 让其返回偶数给鲍勃 同样可以稳操胜券
所以这个题目的答案即 开局是否为奇数或者偶数
动态规划
我们首先尝试把几个数的结果列出 看看有没有规律可循
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 会失败。 ……
假设他们直接的胜负结果是人为的必然关系 （Alice可以选一个数让鲍勃一定失败 鲍勃也可以）
因为N=5这类的之后的数字都可以通过前面的结论获取结果
那么我们就可以根据初始的结论 来循环暴力获取后面的解
保证减去数之后上一个值的解为false就可以保证自己的胜利
解答
数学逻辑
class Solution {
public boolean divisorGame(int n) {
return n%2==0;
}
}
动态规划
class Solution {
public boolean divisorGame(int n) {
//缓存计算结果
boolean[] numResults = new boolean[n+5];
numResults[1] = false;
numResults[2] = true;
//循环获取后面的结果解
for(int i=3;i<=n;++i){ //让i=n 可以让j可以取到n-1
for(int j=1;j<i;++j){ //循环获取可以取的竖
if(i%j==0 && !numResults[i-j]){ //如果值可以整除并且根据之前的结果拿到必赢的方案 true 保证上个结果也就是鲍勃为false
numResults[i] = true;
break;
}
}
}
return numResults[n];
}
}
时空复杂度分析
如果采用逻辑数学解法 时间复杂度为O(1) 空间复杂度为O(1)
如果采用动态规划解法 时间复杂度为O(N^2) 空间复杂度为o(N)
结语
此题涉及到数学的基本定义 并且算一种逻辑数学题 估计掌握这些原理的小学生也可以解出来 足以阐明数学基础的重要性
也涉及到动态规划 如何利用之前的结果来帮助我们寻找定论 虽然我没有真正学过动态规划 不过根据此题 隐隐有点理解 动态规划的特点 (假设一个定论 根据前面的运行结果 循环获取最终结果) 至于这种理解是不是完全正确 等之后真正系统的学习动态规划后再见分晓
