public boolean canWinNim(int n) {
if (n <= 0) {
throw new IllegalArgumentException("n should be greater than 0.");
}
// For stones less than 4, we are already win, cause we can just take all the stones.
if (n < 4) {
return true;
}
// Then, think about the question in this way:
// after choosing 1 ~ 3 stones in the first round,
// can we left AT LEAST ONE deadend to another player?
// For 4 stones, if we choose 1 stone, there are 3 stones left;
// choose 2 stones, 2 stones left;
// choose 3 stones, 1 stone left.
// This is a bad situation for us, but a good news for another player,
// because 1, 2, 3 stones are all not deadends for him.
// So to determine if we can win the game, we only need to care about if we can left AT LEAST ONE deadend at first round.
// For example:
// 5 stones: choose 1 stone, left 4 stones, 4 stones is a deadend so we win;
// 6 stones: choose 2 stones, left 4 stones, win again.
// 7 stones: choose 3 stones, left 4 stones, win again.
// 8 stones: after choosing 1, 2, 3 stones, we left either 5, 6, or 7 stones, and none of them are deadends, so we cannot win the game.
// 9 stones: we choose 1 stone, left 8 stones, 8 stones is a deadend so we win...
// and so on...
// So here comes the DP solution.
boolean[] dp = new boolean[n + 1];
dp[1] = true;
dp[2] = true;
dp[3] = true;
dp[4] = false;
for (int i = 5; i <= n; i++) {
// We choose stones from 1 to 3.
// If there is at least one deadend left, then we can be sure that we can win at `i`;
// otherwise we can just left it as false as a deadend by default.
for (int j = 1; j <= 3; j++) {
if (!dp[i  j]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
Java DP solution with explanation (not acceptable but worth to share)


I think it is enough to maintain the last three status in the code
public class Solution { public boolean canWinNim(int n) { boolean[] dp = {true,true,true}; for(int i=4;i<=n;i++){ if(dp[0] && dp[1] && dp[2]){ dp[0] = dp[1]; dp[1] = dp[2]; dp[2] = false; } else{ dp[0] = dp[1]; dp[1] = dp[2]; dp[2] = true; } } return dp[2]; } }
not acceptable though.

both players play optimally, so if one of three previous dp is true that means he can get manage to get to that state too. So you should strictly check if all of the three previous dp is not true.
for (int i = 5; i <= n; i++) {
bool ret = true;
for (int j = 1; j <= 3; j++) {
if (dp[i  j]) {
ret = false;
}
}
dp[i] = ret;
}But I am afraid this solution gets run out of both time and memory even though it is a nice solution.