题目

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:

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

Example 2:

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

Example 3:

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

Example 4:

  1. Input: n = 7
  2. Output: false
  3. Explanation: Alice can't win the game if Bob plays optimally.
  4. 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). 
  5. 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:

  1. Input: n = 17
  2. Output: false
  3. Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

  • 1 <= n <= 10^5

题意

两人轮流取数，每次只能取走一个平方数，当前回合无法取出平方数的人算输。在都采取最优策略的前提下，判断先取的人是否一定赢。

思路

假设f(n)=true表示总数为n时先取的人能赢。若取走的平方数为k，很明显只要f(n-k)为false(第二个取的人会输)，第一个取的人就能赢。两种实现方式：记忆化搜索和动态规划。

代码实现

Java

记忆化搜索

  1. class Solution {
  2.     public boolean winnerSquareGame(int n) {
  3.         Map<Integer, Boolean> record = new HashMap<>();
  4.         return dfs(n, record);
  5.     }
  7.     private boolean dfs(int n, Map<Integer, Boolean> record) {
  8.         if (n == 0) {
  9.             return false;
  10.         }
  12.         if (record.containsKey(n)) {
  13.             return record.get(n);
  14.         }
  16.         for (int i = 1; i*i <= n;i++) {
  17.             if (!dfs(n - i * i, record)) {
  18.                 record.put(n, true);
  19.                 return true;
  20.             }
  21.         }
  23.         record.put(n, false);
  24.         return false;
  25.     }
  26. }

动态规划

  1. class Solution {
  2.     public boolean winnerSquareGame(int n) {
  3.         boolean[] dp = new boolean[n + 1];
  4.         for (int i = 1; i <= n; i++) {
  5.             for (int j = 1; j * j <= i; j++) {
  6.                 if (!dp[i - j * j]) {
  7.                     dp[i] = true;
  8.                     break;
  9.                 }
  10.             }
  11.         }
  12.         return dp[n];
  13.     }
  14. }