题目地址：https://leetcode.com/problems/divisor-game/
题目描述
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number N on the chalkboard. On each player's turn, that player makes a move consisting of:
1、 Choosinganyxwith0<x<NandN%x==0.；
2、 ReplacingthenumberNonthechalkboardwithN-x.；
Also, if a player cannot make a move, they lose the game.
Return True if and only if Alice wins the game, assuming both players play optimally.
Example 1:
Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.
Example 2:
Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Note:
- 1 <= N <= 1000
题目大意
对于数字N，做两个操作：1. 找出一个因数x，2. 把N换成N - x。两个人轮流做这个操作，问第一个人是否能赢。
解题方法
找规律
首先说结论：当N是偶数时第一个人一定赢，当N是奇数时第一个一定输。
1、 奇数的因子只有奇数，偶数的因子至少一个偶数2；
2、 奇数-奇数=偶数；
3、 当Alice的值是N时必输，则当Alice的值是N+1时必赢(拿1即可)；
那么，当N为下列数字时，先发的状态如下。 当N=1，输； 当N=2，赢（性质3）； 当N=3，输（性质1和2，对方一定是偶数，上面的偶数情况都赢）； 当N=4，赢（性质3）； 当N=5，输（性质1和2，对方一定是偶数，上面的偶数情况都赢）； ... 所以，N为偶数都赢，N为奇数都输。
C++代码如下：
class Solution {
public:
bool divisorGame(int N) {
return N % 2 == 0;
}
};
1 2 3 4 5 6
动态规划
动态规划就是很朴素的做法了，对每个位置i，遍历其因数x，判断N-x的状态，当N-x为输的时候自己赢。
C++代码如下：
class Solution {
public:
bool divisorGame(int N) {
if (N == 1) return false;
if (N == 2) return true;
vector<bool> dp(N, false);
dp[1] = true;
for (int i = 3; i <= N; ++i) {
for (int j = 1; j < i; ++j) {
if (i % j == 0 && !dp[i - j - 1]) {
dp[i - 1] = true;
break;
}
}
}
return dp[N - 1];
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
参考资料：https://leetcode.com/problems/divisor-game/discuss/368269/C%2B%2B-100-and-96-and
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发