算法题-动态规划类型

看题目 除数博弈

将问题拆解

如何得到值?

爱丽丝 true 鲍勃 false；

仔细观察可以看出爱丽丝代表偶数的轮询次数

鲍勃是奇数

例子1 n=2 爱丽丝胜

例子2 n=3 鲍伯胜

如何去定义任意的数字x？

由提示和条件 1 <= N <= 1000； 0 < x < N且N % x == 0

可以得到x可以为1 当N=1时游戏直接结束。。

按照逻辑开整

public static boolean divisorGame(int N) {
    boolean flag=true;
        int i=0;
        //定义x 可知n大于1
        int x=1;
        if(N==1)
        {
            return false;
        }
        //无论n等于几 由条件1 <= N <= 1000 x第一次等于1是没有问题的
        for(;N==0;i++)
        {
            if(N%x==0){
                N-=x;
            }
        }
        if((N&1)==1){ flag=false;}

        return flag;
    }

然后。。

我特么总觉得不对 根据 1234的结果规律

这尼玛好像就是判断n偶奇而已。。

public boolean divisorGame(int N) {
  
  
    if((N&1)==1)
    {
         return false;
    }

    return true;
}

结果还是一样 我心态崩了。。

看大佬的题解

数字N如果是奇数，它的约数必然都是奇数；若为偶数，则其约数可奇可偶。
无论N初始为多大的值，游戏最终只会进行到N=2时结束，那么谁轮到N=2时谁就会赢。
因为爱丽丝先手，N初始若为偶数，爱丽丝则只需一直选1，使鲍勃一直面临N为奇数的情况，这样爱丽丝稳赢；
N初始若为奇数，那么爱丽丝第一次选完之后N必为偶数，那么鲍勃只需一直选1就会稳赢。
综述，判断N是奇数还是偶数，即可得出最终结果！

作者：coder233
链接：https://leetcode-cn.com/problems/divisor-game/solution/qi-shi-shi-yi-dao-shu-xue-ti-by-coder233/
来源：力扣（LeetCode）