假设有两个玩家 Amal 和 Bimal,他们正在玩游戏,Amal 先开始。最初,一堆不同的石头。在每个玩家的回合中,他进行一次移动,包括从堆中移除任何平方数(非零)的石头。此外,如果一个玩家无法移动,他就会输掉比赛。所以如果我们有n,我们必须检查Amal是否能赢得比赛。
因此,如果输入类似于 n = 21,那么输出将为 True,因为首先 Amal 可以取 16,然后 Bimal 取 4,然后 Amal 取 1 并赢得比赛。
让我们看下面的实现来更好地理解
def solve(n): squares = [] square = 1 increase = 3 while square <= n: squares.append(square) square += increase increase += 2 squares.append(square) dp = [None] * (n + 1) dp[0] = False for k in range(1, n + 1): s = 0 dp[k] = False while squares[s] <= k and not dp[k]: if not dp[k - squares[s]]: dp[k] = True s += 1 return dp[-1] n = 21 print(solve(n))
21输出结果
True