LeetCode 509：斐波那契数字“不可下标的int对象”

Question

LeetCode 509: Fibonacci Number

class Solution:
    def fib(self, N: int) -> int:

        if N == 0:
            return 0
        if N == 1:
            return 1

        memo = [None] * (N+1)

        return self.recurse(N, memo)

    def recurse(self, N: int, memo: List) -> int:

        if N == 0:
            return 0
        elif N == 1:
            return 1
        elif memo[N] != None:
            return memo[N]

        memo[N] = self.recurse(N-1, N-2)

        return memo[N]

我在“ elif memo [n]！= None：”行遇到“无法下标的int对象”错误。但是，备注是列表而不是整数。我不知道为什么会收到此错误。也许与我用所有None元素初始化List的事实有关？任何帮助，将不胜感激。谢谢！

Answer 1

您在这里：

from typing import List

class Solution:
    def fib(self, N: int) -> int:
        if N == 0: return 0
        elif N == 1: return 1
        memo = [None] * (N+1)
        memo[0] = 0
        memo[1] = 1
        return self.recurse(N, memo)

    def recurse(self, N: int, memo: List) -> int:
        if memo[N] is not None:
            return memo[N]
        memo[N] = self.recurse(N - 1, memo) + self.recurse(N - 2, memo)
        return memo[N]

solution = Solution()
for i in range(10):
    print(f'fib({i}) = {solution.fib(i)}')

输出：

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34