1
class Solution {
2
  // idea: Alice wins a game with n stones if and only if there exists
3
  // some perfect square p <= n such that Alice wins a game with
4
  // n - p stones... i.e., Bob DOES NOT win a game with n - p stones
5
  public boolean winnerSquareGame(int n) {
6
    // this bit would be better with just an array of booleans, but this
7
    // is how i thought of it at the time, so leaving it this way...
8
    // maybe it will be "more explicit" and help someone better understand dp?
9
    HashMap<Integer, Boolean> memo = new HashMap<>();
10
    memo.put(
11
        1, true); // if there is one stone in the pile to begin the game, the next player to go wins
12
    memo.put(
13
        0, false); // if there are zero stones in the pile to begin the game, the next player to go
14
    // loses
15
    List<Integer> perfectSquares = new ArrayList<>();
16
    int i = 1;
17
    while (i * i <= n) {
18
      perfectSquares.add(i * i);
19
      i++;
20
    }
21
    // if there are some perfect square number of stones in the pile to begin the game, the next
22
    // player to go wins
23
    perfectSquares.forEach(p -> memo.put(p, true));
24
    // Alice goes first...
25
    return this.playerWins(n, perfectSquares, memo);
26
  }
27

28
  private boolean playerWins(int n, List<Integer> P, HashMap<Integer, Boolean> m) {
29
    if (m.containsKey(n)) {
30
      return m.get(n);
31
    } // if we already computed the answer for n, just return it
32
    m.put(n, false); // otherwise, assume it's false to begin...
33
    for (Integer p : P) { // check every perfect square p...
34
      if (p <= n && !playerWins(n - p, P, m)) {
35
        // if p <= n AND the player who goes next (e.g., Bob) does not win a game that begins with
36
        // n - p stones, then we know that the player whose turn it is right now (e.g., Alice) wins
37
        // a game that begins with n stones, so record this discovery in the memo and then break out
38
        // of the loop because there's no more work to do...
39
        m.put(n, true);
40
        break;
41
      } // else p >= n OR taking p stones would not result in a win for the player whose turn it is
42
      // right now...
43
    }
44
    // we put false in before the loop; if we never found a reason to change it to true,
45
    // then false is the correct result...
46
    return m.get(n);
47
  }
48
}