1025. 除数博弈

题目描述

1.1、动态规划

记dp[N]为黑板上数字为N的情况下,Alice的输赢情况， 如果Alice取了数字x, 那么显然dp[N]与dp[N -x]输赢情况相反。 x可以取的值很多，只要dp[N -xi]中任意一个为False, 那么dp[N]肯定为True, 否则dp[N]肯定为False

class Solution:
    def divisorGame(self, N: int) -> bool:
        dp = {}
        dp[1] = False
        dp[2] = True
        for i in range(3, N+1):
            for j in range(1, i//2+1):
                dp[i] = False
                if i % j ==0 and dp[i-j] == False:
                    dp[i] = True
                    break
            
        return dp[N]

1.2、奇偶法

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