2 人游戏从给定数字中减去完全平方数的算法

Question

我需要一些帮助来解决问题。我最近在一次采访中得到了这个问题，我试图解决它，但没有运气。这是问题：

为由两名玩家组成的游戏编写算法。输入是正整数x。每一轮，玩家都会从数字中扣除一个完全平方数。玩家可以选择任何小于或等于当前数字且大于0的完全平方数。如果扣除后数字变为0，则当前玩家获胜。

我想这应该使用动态编程/贪心方法来完成，我不太熟悉这种方法。或者我们可能需要想出一系列获胜/失败的数字，如果玩家最终处于获胜序列，那么无论如何他都会获胜。但我们如何得出这样的序列呢？

谁能帮我用Java解决这个问题？

更新：

DAle 建议的解决方案 1：

public int subtractPerfectSquares(int n)
   {
      if (n <= 0)
         return 1;
      boolean[] isWinningCase = new boolean[n + 1];

      for (int i = 1; i <= n; i++)
      {
         for (int num = 1; num * num <= i; num++)
         {
            if (!isWinningCase[i - (num * num)])
            {
               isWinningCase[i] = true;
               break;
            }
         }
      }

      return isWinningCase[n] ? 1 : 2;
   }

为了更好地理解，修改了解决方案2：

 public int subtractPerfectSquares2(int n)
   {
      if (n <= 0)
         return 1;
      boolean[] isWinningCase = new boolean[n + 1];

      // if we reach 0, we win
      isWinningCase[0] = true;
      // 1 is a win 
      isWinningCase[1] = true;
      // 2 is a losing condition. We must define this as this state dictates losing scenarios for further states
      isWinningCase[2] = false;

      // we start from 3
      for (int i = 3; i <= n; i++)
      {
         for (int num = 1; num * num <= i; num++)
         {
            int prefectSquare = num * num;
            // if we get to 0 from current number or if we get to a losing scenario (to be faced by next player) from current number, then the current state is a winning position
            if (i - prefectSquare == 0 || !isWinningCase[i - prefectSquare])
            {
               isWinningCase[i] = true;
               break;
            }
         }
      }

      // return player 1 if given number is a winning state else player 2 wins
      return isWinningCase[n] ? 1 : 2;
   }

Answer 1

在这个游戏中，玩家之间的唯一区别是玩家 1 先走。这种类型的博弈称为公平博弈，双方玩家的完美策略是相同的。此外，我们可以x使用以下规则将游戏的所有状态（整数）分为两种类型：获胜位置或失败位置：

1. x=0是一个失败的位置
2. 如果至少有一种可能的举动导致失败，那么该位置x就是获胜位置。
3. x如果每一个可能的举动都会导致获胜位置，那么该位置就是失败位置。

1然后我们需要确定从到 的所有仓位的类型x。可能的实施：

boolean[] isWinning = new boolean[x+1];
for (int state = 0; state <= x; ++state) {
    isWinning[state] = false;
    for (int i = 1; i*i <= state; ++i) {
        int perfectSquare = i*i;
        if (!isWinning[state - perfectSquare]) {
            isWinning[state] = true;
            break;
        }
    }
}

如果当前玩家处于获胜位置 ( isWinning[x] == true)，则应选择这样的完全平方isWinning[x - perfectSquare] == false。这将使游戏（和其他玩家）陷入失败的境地。如果玩家处于失败的位置，没有什么可以拯救他，每一个可能的完美方块都同样糟糕。