LeetCode 509: Fibonacci Number "int object not subscriptable"

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]

I am getting an "int object not subscriptable" error on the line "elif memo[n] != None:". However, memo is a list not an int. I can't figure out why I am getting this error. Maybe it has to do with the fact that I initialized my List with all None elements? Any help would be appreciated. Thank you!

Answer 1

Here you go:

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)}')

Output:

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