1
// DP problem
2
var winnerSquareGame = function (n) {
3
  //             //////////////////////////////////
4
  //     1. Define an array that Alice will win or loss (T/F)
5
  //             //////////////////////////////////
6

7
  const res = new Array(n + 1).fill(false);
8
  let k = 1;
9

10
  for (let i = 1; i <= n; i++) {
11
    //             //////////////////////////////////
12
    //     2. if it is square number, obviously, Alice win
13
    //             //////////////////////////////////
14

15
    if (k * k === i) {
16
      res[i] = true;
17
      k++;
18
      continue;
19
    }
20

21
    //             //////////////////////////////////
22
    //     3. after Alice removes j*j (1 <= j < k) stones, find whether res[i-j*j] is T/F (= Bob win/loss)
23
    //        if j exists that res[i-j*j] = false, it means that Bob will lose the game with the remaining i-j*j stones => Alice wins
24
    //        otherwise, Alice lose
25
    //             //////////////////////////////////
26

27
    let AliceWin = false;
28
    for (let j = 1; j < k && j * j <= i; j++) {
29
      if (!res[i - j * j]) {
30
        AliceWin = true;
31
        break;
32
      }
33
    }
34
    res[i] = AliceWin;
35
  }
36

37
  return res[n];
38
};