1025. 除数博弈

题目地址

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;
    }
}