LC 1025. Divisor Game

https://leetcode.com/problems/divisor-game/

我在讨论区里面写了 自己的解法，直接粘贴过来吧。虽然一开始使用DP解决了这个问题，但是既然标签难度是Easy的，所以估计还有更容易的解法。

classical dp solution would be:

• dp[x] represents "if I starts with X stones, will I win?"
• dp[x] = 1 iff. there is y st. x % y == 0 and dp[x-y] ==0
• otherwise dp[x] = 0

so the code would be

class Solution:
    def divisorGame(self, N: int) -> bool:
        dp = [-1] * (N + 1)

        def search(n):
            if dp[n] != -1:
                return dp[n]

            ans = 0
            for x in range(1, n):
                if n % x != 0: continue
                if search(n - x) == 0:
                    ans = 1
                    break
            dp[n] = ans
            return ans
        print(dp)
        ans = search(N)
        return ans

But if you watch dp closely, looks like there is a pattern. You will win at even number, and lose at odd number. So you would come accorss a intuition and guess a simple solution return N % 2 == 0 . Fortunately the guess is correct.

The explanation is followed. Let's start with base situation

1. N==2. apparently it's true.
2. if N is even number, then N % 2 == 0, we can get 2 stones. So the case is N-2, which is still a even number, and we still win.
3. if N is odd number, and assume there is a x st. N % x == 0. x must be a odd number. So the case is N-x, which is a even number, and we lose.

所以最后的代码非常简单

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