名称___未定义-递归斐波那契记忆

Question

NameError: name 'fib_cache' is not defined

因此，我试图使用记忆来实现斐波那契数列，但我在leetcode中不断收到这个错误，我不知道为什么。有人能给我指正确的方向吗？

class Solution:

fib_cache = {}

def fib(self, n: int) -> int:

value;

if n <=1:
value = n;
elif n>2:
value = fib(n-1) + fib(n-2);

fib_cache[n] = value
return value

Answer 1

我修复了代码中的一些行，现在它可以工作了。实际上，你在代码中没有使用记忆，所以我也解决了这个问题。

class Solution:

fib_cache = {}

def fib(self, n: int) -> int:

value = 0  # You don't need this line
if n in Solution.fib_cache:  # this adds the memoziation idea
return Solution.fib_cache[n]
if n <=1:
value = n
elif n>=2:   # <==== Fixed this line
value = self.fib(n-1) + self.fib(n-2)   # <==== Fixed this line

Solution.fib_cache[n] = value  # <==== Fixed this line
return value
s = Solution()   # You don't need these 2 lines in leetcode
print(s.fib(5))   #  I wrote them for testing

输出：5