# 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 ansBut 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

- N==2. apparently it's true.
- 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.
- 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