leetcode 1510 - Stone Game IV

https://leetcode.com/problems/stone-game-iv/

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn’t have any moves.
Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).
Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).
Example 4:

Input: n = 7
Output: false
Explanation: Alice can’t win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0).
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).
Example 5:

Input: n = 17
Output: false
Explanation: Alice can’t win the game if Bob plays optimally.

Constraints:

1 <= n <= 10^5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//Recursive
class Solution {
public:
bool winnerSquareGame(int n) {
vector<int> memo(n+1, -1);

int move = winnerSquareGame(n, memo);

return move > 0;
}

int winnerSquareGame(int n, vector<int> &memo) {
int move;

if (n == 0) return 0;

if (memo[n] != -1) return memo[n];

for (int i = 1; i*i <= n; i++) {
move = 1 - winnerSquareGame(n - i * i, memo);

if (move > 0)
break;
}

memo[n] = move;
return move;
}
};

//DP
class Solution {
public:
bool winnerSquareGame(int n) {
vector<int> dp(n+1);
dp[0] = 0;

for (int i = 1; i <= n; i++) {
int move;
for (int j = 1; j*j <= i; j++) {
move = 1 - dp[i - j*j];
if (move > 0)
break;
}

dp[i] = move;
}

return dp[n] > 0;
}
};