Problems in memoization Fibonacci sequences in Python

Question

I am implementing a Fibonacci sequence with Python. And I used an array ("[]") for memoization, but I get an IndexError: list assignment index out of range.

However, using an object ("{}") works fine. What's the difference?

code

def fib(n):
    if n <= 1:
        memo[n] = n

    if n not in memo:
        memo[n] = fib(n-2) + fib(n-1)

    return memo[n]


# memo = [] not work.
# memo = {} work.

print(fib(6))

Possible duplicate of [What is the difference between {} and \[\] in python?](https://stackoverflow.com/questions/5230874/what-is-the-difference-between-and-in-python) — Rahul Agarwal, Apr 12 '19 at 09:20
`[]` creates a `list`, while `{}` creates a `dict`. A `list` is just an array, with contiguous elements. There are no holes in a list. A `dict` is a hash table. It's less efficient than a `list`, but it only requires storage for the elements that you need (plus some overhead), and the keys can be any un-mutable values (not just integers). — Tom Karzes, Apr 12 '19 at 09:23

Umesh · Accepted Answer · 2019-04-12T09:32:38.173

0

when you do memo = [] it doesn't have any elements in it. and when you send fib(2) its actually doing

memo[2] = n

which will throw an error list index out of range, because memo doesnt have any element at index 2

When you do memo = {}, its creating a dict and

memo[2] = n

will add a new key 2 with value n it it. like this:

memo = {
  2: n
}

edited Apr 12 '19 at 09:32

answered Apr 12 '19 at 09:26

Umesh

941
5
12

Problems in memoization Fibonacci sequences in Python

1 Answers1