爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字
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
解法一
//时间复杂度O(?), 空间复杂度O(?)
class Solution {
public:
bool can_win(int N, vector<int>& rec) {
//if(N <= 1) return false;
for(int i = 1; i <= N / 2; i++) {//尝试每一个能整除的数
if(N % i == 0 ) {
if(rec[N - i] == 0) {//选i时，下一回合对手会输，我就赢了
rec[N] = 1;
return true;
}
else if(rec[N - i] == -1) {//未知
rec[N] = !can_win(N - i, rec);
return rec[N];
}
else continue;//选i必输，试下一个数
}
}
rec[N] = 0;//尝试过了所有能除尽的数字，都不能赢。那输定了
return false;
}
bool divisorGame(int N) {
vector<int> rec(N + 1, -1);//-1：未知；0：输；1：赢
return can_win(N, rec);
}
};解法二
//时间复杂度O(n), 空间复杂度O(n)
class Solution {
public:
bool divisorGame(int N) {
vector<int> rec(N + 1, 0);
for(int i = 2; i <= N; i++) {
int high = sqrt(i);
for(int j = 1; j <= high; j++) {
if(i % j == 0 && rec[i - j] == 0) {
rec[i] = 1;
goto nexti;
}
}
nexti:;
}
return rec[N];
}
};解法一：
当面临剩余数字为N时，递归遍历所有可能的情况，即尝试所有能整除N的数i（1=<i<N），如果存在一个数i能使对手面临N-i时必输，那自己就能赢。利用这个思路，容易写出如下递归解：
class Solution {
public:
bool divisorGame(int N) {
//if(N <= 1) return false;
for(int i = 1; i <= N / 2; i++) {
if(N % i == 0 && !divisorGame(N - i))
return true;
}
return false;
}
};从思路上看此解是正确的，但是存在大量重复计算。完全可以将其重复子问题只求解一次然后存入表中，后续再遇到直接查表来节约计算量。解决办法是解法一，利用了一个记录rec，rec[N]代表自己面临N个数时是否能赢（0表示必输，1必赢，-1未计算。其中"必输"、"必赢"中必然性的前提是两个人每一步都能做出最优选择，题上已经说明了）。代码如上。
解法二：
可以不使用递归，迭代即可。这里把求整除数的搜索上限改为了sqrt(x)，但是提交结果显示计算更慢了，原因不详。
2019/09/07 23:46