1.想法
1.1动态规划
首先，可以确定选到1的人一定输，为了变成1，前一个人的必须是2，因为其他的数字没法造成1，为了变成2，那么前一个人的选择必须是3，同理推断
next_value = now_value-k;
now_value%k == 0;
| 倒数第N步 | 赢方 | 输方 |
|---|---|---|
| 1 | 1 | |
| 2 | 2 | |
| 3 | 3 | |
| 4 | 4/6 | |
| 5 | 5 |
因为两个人都是极度聪明的，所以后一个的选择必须是惟一的且必须是一定输的，这样才能前一个人的选择是赢的。那么我们从底层推测，
例：1.当前的数字为1的时候则一定输，
2.对于前一个数字2来说，因为这两个人不会犯错，所以一定让下一个数字为1，则当前为2 的人一定赢。
3.同理当前为3的人一定输
4.所以当为4的时候可以变成3和2，则若为2则一定输，为3则一定赢，那么此时一定选择变成3，则一定赢。
5.而对于5来说和4正好相反，因为多了一步，5只能改变成4，
6.而对于6来说，可以变成5和4和3，选择中5，3必输，4必赢。
那么就是说子选项中存在一个必赢的选择，则一定赢，否则一定输
那么我们定义F[n] = 必赢(true) ,存在（n-i）使得n%i==0且F[n-i] =必输(false)
归纳公式为：
1.1代码
class Solution {
public boolean divisorGame(int N) {
boolean[] result = new boolean[N+1];
result[1] = false;
for(int i=2;i<N+1;i++){
int temp = (int) Math.pow(i,((double)1)/2);
boolean flag = false;
for(int j = 1;j<=temp;j++){
if(i%j==0&&!result[i-j]){
flag = true;
}
}
result[i] = flag;
}
return result[N];
}
}
1.2总结法
奇数的约数也是奇数，奇数减奇数就是偶数，那么偶数在不考虑时间的情况下每次都-1，另一个人得到的一定是奇数，那么拿到奇数的人无论怎么处理返回给上一个人的一定是偶数，那么拿到偶数的人一定是胜利的，因为一定拿到2，而拿到奇数的人一定是失败的因为手上一定是1。
1.2代码
class Solution {
public boolean divisorGame(int N) {
return N%2 == 0;
}
}
