先找边界:SG[0] = 0表示当石子数为0时,先手输
然后套SG即可
若为n堆,每堆的SG异或即可
class Solution { public: int SG[100001]; int vis[100]; bool winnerSquareGame(int n) { SG[0] = 0; for(int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); for(int j = 1; j * j <= i; j++) vis[SG[i - j * j]] = 1; for(int j = 0; ; j++) if(!vis[j]) { SG[i] = j; break; } } return SG[n]; } };