LeetCode 509: Fibonacci Number "int object not subscriptable"

Question

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!

Here: memo[N] = self.recurse(N-1, N-2) you pass a number as the second argument to recurse, so memo is a number, not a list. — Błotosmętek
– Błotosmętek, Commented Jun 5, 2020 at 10:02
Ah Thank you. I meant to write memo[N] = self.recurse(N-1, memo) + self.recurse(N-2, memo). Dumb mistake. Thank you — Bao Pham
– Bao Pham, Commented Jun 5, 2020 at 10:03

Balaji Ambresh · Accepted Answer · 2020-06-05 10:09:08Z

2

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

answered Jun 5, 2020 at 10:09

Balaji Ambresh

5,0022 gold badges7 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

LeetCode 509: Fibonacci Number "int object not subscriptable"

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related