小编Tho*_*s99的帖子

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

为由两名玩家组成的游戏编写算法。输入是正整数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 …