1025. Divisor Game

淡淡的烟草味﹌ 2024-03-23 12:16 95阅读 0赞

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:

*  Choosing any `x` with `0 < x < n` and `n % x == 0`.
 *  Replacing the number `n` on the chalkboard with `n - 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: n = 2
    Output: true
    Explanation: Alice chooses 1, and Bob has no more moves.

**Example 2:**

Input: n = 3
    Output: false
    Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

**Constraints:**

*  `1 <= n <= 1000`

很久没刷题了，今天好不容易偷了点时间刷了几道题。首选DP问题。

题目：Alice和Bob玩游戏，Alice开局。最初黑板上有个数字n，每一轮玩家需要：

1，选择一个x, 0 < x < n，满足n % x == 0

2, 将黑板上的数字n替换为n-x。

当玩家不能再继续往下走的时候，游戏结束。

当只能Alice赢的时候返回true，假设两个玩家都非常聪明。也就是两个玩家都想尽办法的赢对方。

思路：看到题目限制1<=n<=1000，可以接收n^2的时间复杂度，因此大胆的用DP方法。本题的点在找x。也就是说只有在给对方剩下的黑板上的数字是 n-x时，对方不管怎样走都会输的时候，自己才会赢。因此只要从n-1开始往前遍历到1找到这个x即可，x需要满足条件n%x==0。

问题可以举例为：

1） 当n = 1时，Alice走不动，因此Alice输，返回false

2） 当n = 2时，Alice只能选择1， 此时Bob剩1，根据1）所述，Bob输，返回true

3） 当n = 3时，Alice只能选择1，根据 2）所述，Bob赢，Alice输，返回false

4） 当n = 4时，Alice可以选择1或2，剩2或3，当剩下3时，根据3）Bob输，Alice赢，返回true

......

因此可以用一个长度为n+1的数组储存0~n时Alice的输赢状态，每次往前遍历即可。代码：

class Solution {
    public:
        bool divisorGame(int n) {
            vector<bool> result(n+1, false);
            for(int i = 2; i <= n; i++){
                for(int j = 1; j < i; j++){
                    if(i % j != 0) continue;
                    if(result[i - j] == false){
                        result[i] = true;
                        break;
                    }
                }
            }
            return result[n];
        }
    };

还有个简单方法，但我不理解~~~感觉跟DP没关系：

class Solution {
    public:
        bool divisorGame(int N) {
            return N%2==0;
        }
    };