Fibonacci Memoization return list from 0 to N-CodePudding

def fib(n, memo: Dict = {}):
    if n == 0 or n == 1:
        return n
    if n not in memo:
        memo[n] = fib(n-2, memo) fib(n-1, memo)
    return memo[n]

I have this function that uses memoization which returns the nth digit of the fibonacci sequence. How do I modify this function so that it returns a list of values from 0th to Nth fibonacci sequence? I still want to use memoization.

Input: 10

Current input: 55

Wanted output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

EDIT: This solution works

from typing import Dict, List


def fib(n, res: List = [], memo: Dict = {}):
    fib_helper(n, res, memo)
    if n >= 1:
        res.insert(1, 1)
    if n >= 0:
        res.insert(0, 0)
    return res


def fib_helper(n, res, memo):
    if n == 0 or n == 1:
        return n
    if n not in memo:
        memo[n] = fib_helper(n-2, res, memo) fib_helper(n-1, res, memo)
        res.append(memo[n])
    return memo[n]

CodePudding user response：

Pass a dict to this function as follows:

mydict= {}
fib(10,mydict)
list(mydict.values())

In case you don't get 0 or 1, modify it as follows. Output of the modified code.

>>> def fib(n, memo):
...     if n == 0 or n == 1:
...             memo[n] = n
...             return n
...     if n not in memo:
...             memo[n] = fib(n-2, memo) fib(n-1, memo)
...     return memo[n]
...
>>> mydict = {}
>>> fib(10, mydict)
55
>>> list(mydict.values())
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

CodePudding user response：

Take advantage of the facility offerred by functools.lru_cache (you should check your input in non negative somewhere):

import functools

@functools.lru_cache()
def fibonacci(n):
    if n <= 2:
        return 0 if n == 0 else 1
    return fibonacci(n-1)   fibonacci(n-2)


your_input = 10

print([fibonacci(x) for x in range(your_input   1)])

CodePudding user response：

It would be easier without the recursion.

memo = [0, 1]

def fib(n): # n is a non-negative int
    n  = 1  # 0 to n incl. is [0:n 1]
    missing = n - len(memo)
    if missing > 0:
        a, b = memo[-2:]
        for _ in range(missing):
            a, b = b, a b 
            memo.append(b)
    return memo[:n]

print(fib(10))  # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]