1510.Stone Game IV¶

1510.Stone Game IV¶

Tags: Hard Dynamic Programming

Links: https://leetcode.com/problems/stone-game-iv/

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

1 <= n <= 10^5

这道题让我联想到了279.Perfect Squares的四平方和定理，虽然并没有什么作用。

一个策略就是尝试所有小于n的平方数，看能否获胜，比如先尝试1，余下的就是n - 1，那么就变成了对手在n - 1的情况下先手能否获胜。那么如果我知道了在n-1情况下先手能否获胜，就可以直接得出结果。很自然的，想到用递归求解。但是注意到会存在很多重复计算，那么想到用动态规划来解决重复计算的情况。

用d[i]表示石子数量为i时先手能否获胜，i = 1, 2时可以直接得出结果。首先如果这个数本身就是完全平方数，直接取走所有的石子，先手必胜。如果一个数不是完全平方数，并且要求每次必须取完全平方数的数量的石子，所以我们尝试所有小于等于n的完全平方数，假设取走的完全平方数是k，那么余下的就是n - k，只有此时n-k先手必输的情况下，先手取走k是一个必胜的策略。

于是我们预处理出所有不超过 $10^5$ 的完全平方数，对于循环遍历到i，用二分查找的办法找到最后一个不超过i的完全平方数（也就是第一个大于i的位置的前一个位置），需要搜索的长度为 $\sqrt n$ ，所以时间复杂度 $O(n(\sqrt{n} + \log{n}))$ 。

class Solution {
public:
    bool winnerSquareGame(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (n == 1) return true;
        if (n == 2) return false;

        vector<int> d(n + 1, 0);
        d[1] = 1; d[2] = 0;

        vector<int> seq;
        int cnt = 1;
        int limit = 1e5;
        while (cnt * cnt <= limit) {
            seq.push_back(cnt * cnt);
            ++cnt;
        }

        for (int i = 3; i <= n; ++i) {
            if (isSuqare(i)) {
                d[i] = 1;
            }
            else {
                int pos = (upper_bound(seq.begin(), seq.end(), i) - seq.begin()) - 1;
                for (int j = 0; j <= pos; ++j) {
                    if (!d[i - seq[j]]) { d[i] = 1; break; }
                }
            }
        }

        return d[n];
    }

    bool isSuqare(int n)
    {
        int k = sqrt(n);
        return k * k == n;
    }
};