https://leetcode-cn.com/problems/divisor-game/ 思路一： d p dp dp，不妨设 d p [ i ] dp[i] dp[i]表示数字为 i i i时，爱丽丝能否胜利。那么显然有 d p [ 1 ] = f a l s e dp[1]=false dp[1]=false， d p [ 2 ] = t r u e dp[2]=true dp[2]=true，对于任意的 3 < = i < = N 3<=i<=N 3<=i<=N，对于其任意一个因子 j j j显然有 d p [ i ] = d p [ i ] ∣ ∣ d p [ i − j ] dp[i]=dp[i]||dp[i-j] dp[i]=dp[i]∣∣dp[i−j]。
class Solution { public: bool divisorGame(int N) { if(N==1) return false; if(N==2) return true; vector<bool> dp(N+1); dp[0]=true; for(int i=3;i<=N;i++){ int tmp=sqrt(i); for(int j=1;j<tmp&&!dp[i];j++){ if(i%j==0){ dp[i]=!dp[i-j]; if(!dp[i]) dp[i]=!dp[i-i/j]; } } } return dp[N]; } };思路二：找规律或者说递推？首先要知道奇数只能拆成奇数和奇数的乘积，那么从 3 3 3开始递推下去，不难发现偶数必胜，奇数必败。
class Solution { public: bool divisorGame(int N) { return !(N&1); } };