Fibonacci Memoization return 列表从 0 到 N

Question

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]

我有一个使用记忆的函数，returns 斐波那契数列的 第 n 位 。我如何修改此函数，使其 returns 是从第 0 到第 N 个斐波那契数列的值列表？我还是想用memoization

输入：10

当前输入：55

想要的输出：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

编辑：此解决方案有效

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]

Answer 1

按如下方式将字典传递给此函数：

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

如果没有得到0或1，修改如下。修改后代码的输出。

>>> 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]

Answer 2

利用 functools.lru_cache 提供的便利（您应该在某处检查您的非负输入）：

import functools

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


your_input = 10

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

Answer 3

没有递归会更容易。

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]

Fibonacci Memoization return 列表从 0 到 N

Fibonacci Memoization return list from 0 to N

python

algorithm

hashmap

memoization

dynamic-programming