如何修改带memoization的斐波那契函数以返回0到第N项序列列表

原有函数仅返回第n项的斐波那契值，要保留记忆化逻辑的同时返回从第0项到第n项的完整序列，只需要在记忆化存储计算结果的同时，把每一步算出的项按顺序收集到列表里，最后补全前两项即可。

完整可运行实现 #

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]

测试效果 #

输入10时，输出为期望结果：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

逻辑说明 #

• 完全保留了原有的memo字典记忆化逻辑，已计算过的项不会重复计算，时间复杂度仍为O(n)
• 新增res列表用来收集递归过程中计算出的≥2的斐波那契项
• 递归结束后手动补入第0项的0和第1项的1，即可得到从0到n的完整序列

优化点（可选） #

Python中可变默认参数是函数定义时初始化的，多次调用会有参数残留问题，如果要避免该问题，可以调整参数初始化逻辑：

from typing import Dict, List, Optional

def fib(n: int, res: Optional[List] = None, memo: Optional[Dict] = None) -> List:
    if res is None:
        res = []
    if memo is None:
        memo = {}
    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: int, res: List, memo: Dict) -> int:
    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]

调整后每次调用不传res和memo时，都会生成新的空列表和字典，多次调用不会互相干扰。

内容的提问来源于stack exchange，提问作者Paolo Tormon