Q1025 除数博弈-简单-动态规划

1025. 除数博弈

Question

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 x，满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。

Example 1:

输入：2 输出：true 解释：爱丽丝选择 1，鲍勃无法进行操作。

Example 2:

输入：3 输出：false 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

提示：

1 <= N <= 1000

Approach 1: 归纳法

博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：

N=1 的时候，区间 (0, 1) 中没有整数是 n 的因数，所以此时败。
N = 2 的时候，只能拿 1，N 变成 1，无法继续操作，故胜。
N = 3 的时候，只能拿 1，N 变成 2 ，根据 N = 2 的结论，我们知道此时会获胜，败。
N = 4 的时候，能拿 1 或 2 ，如果拿 1，根据 N=3 的结论，会失败，会获胜。
N=5 的时候，只能拿 1，根据 N=4 的结论，会失败。 ......

写到这里，也许你有了一些猜想。没关系，请大胆地猜想，在这种情况下大胆地猜想是 AC 的第一步。也许你会发现这样一个现象：N 为奇数的时候（先手）必败，N 为偶数的时候必胜。这个猜想是否正确呢？下面我们来想办法证明它。

证明

和时结论成立。
时，假设时该结论成立，则时：
- 如果 k 为偶数，则为奇数，x 是的因数，只可能是奇数，而奇数减去奇数等于偶数，且，故轮到的时候都是偶数。而根据我们的猜想假设的时候偶数的时候先手必胜，故此时无论拿走什么，都会处于必胜态，所以处于必败态。
- 如果 k 为奇数，则 k + 1 为偶数，x 可以是奇数也可以是偶数，若减去一个奇数，那么是一个小于等于的奇数，此时占有它，处于必败态，则处于必胜态。综上所述，这个猜想是正确的。

下面是代码实现。

class Solution:
    def divisorGame(self, N: int) -> bool:
        return N % 2 == 0


def main():
    N = 5
    solution=Solution().divisorGame(N)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：
空间复杂度：

Approach 2: 动态规划

在「方法一」中，我们写出了前面几项的答案，在这个过程中我们发现，处在的状态时，他（她）做一步操作，必然使得 Bob 处于 N = m (m < k) 的状态。因此我们只要看是否存在一个 m 是必败的状态，那么 Alice 直接执行对应的操作让当前的数字变成 m，就必胜了，如果没有任何一个是必败的状态的话，说明无论怎么进行操作，最后都会让处于必胜的状态，此时是必败的。

结合以上我们定义表示当前数字 i 的时候先手是处于必胜态还是必败态，表示先手必胜，表示先手必败，从前往后递推，根据我们上文的分析，枚举 i 在 (0, i) 中 i 的因数 j ，看是否存在为必败态即可。

def divisorGame1(self, N: int) -> bool:
    f=[False]*(N+5)
    f[1]=False
    f[2]=True
    for i in range(3,N+1):
        for j in range(1,i):
            if i%j==0 and not(f[i-j]):
                f[i]=True
                break
    return f[N]

复杂度分析

时间复杂度：。递推的时候一共有 n 个状态要计算，每个状态需要的时间枚举因数，因此总时间复杂度为
空间复杂度：。我们需要的空间存储递推数组 f 的值。