的MemoryError在本文给出了

稔和游戏我试图解决从https://leetcode.com/problems/nim-game/description/以下问题：的MemoryError在本文给出了

您玩的是以下稔游戏与您的朋友：有石头的桌子上堆，每次你们中的一人轮流移除1至3颗宝石。去掉最后一块石头的人将是胜利者。您将首先转动以移除宝石。

你们俩都很聪明，并且有最佳的游戏策略。编写一个函数，以确定您是否可以在堆中的石块数量的情况下赢得游戏。

例如，如果堆中有4块石头，那么你永远不会赢得比赛：无论你移除的是1块，2块还是3块石头，最后一块石头总是会被你的朋友移除。

我想出了以下解决方案，采用了自下而上的动态规划方法：

class Solution(object): 
    def canWinNim(self, n): 
     """ 
     :type n: int 
     :rtype: bool 
     """ 
     if n <= 3: 
      return True 
     win = [None for _ in range(n+1)] 
     win[1] = win[2] = win[3] = True 
     for n in range(4, n+1): 
      win[n] = not all([win[n-i] for i in [1, 2 ,3]]) 
     return win[n]

然而，当我尝试提交此，我得到一个MemoryError：

由于没有给出这个MemoryError产生的确切测试用例，我正在努力查看是什么导致了这个问题。有任何想法吗？

来源

2017-09-03 Kurt Peek

为什么你会使用范围..你在python 3或2？ – SMA

你认为你可以在内存中保存每个游戏的解决方案，包括n。这是一个有竞争力的网站（我假设），他们不会给你一百万的小数目。 –

而不是为每个游戏生成最多为n的解决方案，也许你可以尝试生成一个让我们假设达到20的解决方案，检查它并查看是否可以找到一个模式。如果有一个你可以利用它来生成n的解决方案，而不必生成所有其他解决方案高达n-1。 – niemmi

事实上，正如Kenny Ostrom所指出的那样，测试用例可能是用于如此大的存储空间不足以存储“自下而上”动态编程方法中生成的答案。通过运行它在一个较小的例子，我注意到，答案很简单

bool(x % 4)

来源

2017-09-03 16:34:33

的MemoryError在本文给出了

回答

相关问题