classSolution{public:boolwinnerSquareGame(intn){// dp[i] := the winning result for n = ivector<bool>dp(n+1);for(inti=1;i<=n;++i)for(intj=1;j*j<=i;++j)if(!dp[i-j*j]){// remove j^2 stones make the opponent losedp[i]=true;// so we winbreak;}returndp[n];}};
1 2 3 4 5 6 7 8 9101112131415
classSolution{publicbooleanwinnerSquareGame(intn){// dp[i] := the winning result for n = iboolean[]dp=newboolean[n+1];for(inti=1;i<=n;++i)for(intj=1;j*j<=i;++j)if(!dp[i-j*j]){// remove j^2 stones make the opponent losedp[i]=true;// so we winbreak;}returndp[n];}}