使用记忆化时嵌套函数返回值异常及DP斐波那契实现优化咨询

一、计数始终返回0的原因及解决方法 #

问题根源 #

你在fibonacci_memoized中返回的count[0]是值的拷贝，而非对列表元素的引用。当函数返回时，count[0]的初始值0被赋值给变量c，后续调用fib_calculation时修改的是闭包内count列表的元素，但c的值不会同步更新，因此始终输出0。

修复代码 #

将返回值改为返回count列表本身，这样后续可以通过列表访问更新后的计数：

def fibonacci_memoized():
    cached = {}
    count = [0]

    def fib(n):
        count[0] += 1
        if n in cached:
            return cached[n]
        elif n < 2:
            cached[n] = n
            return n
        elif n >= 2:
            cached[n] = fib(n-1) + fib(n-2)
            return cached[n]

    return fib, count


fib_calculation, count_list = fibonacci_memoized()
given_index = 7  # 对应输出结果13的索引
result = fib_calculation(given_index)
print("Memoized recursive Fibonacci sequence solution:", result, "Execution:", count_list[0])

二、当前实现的合理性 #

这种闭包封装记忆化缓存和计数的实现是合理的：

• 利用闭包避免了全局变量，将缓存和计数逻辑封装在函数内部，保证了代码的模块化和安全性；
• 手动维护缓存的方式清晰展示了记忆化的核心逻辑，适合理解动态规划的原理。

三、代码优化方向 #

1. 使用functools.lru_cache简化记忆化 #

Python标准库的lru_cache装饰器可以自动实现记忆化，无需手动维护cached字典，大幅简化代码：

from functools import lru_cache

def fibonacci_memoized():
    count = [0]

    @lru_cache(maxsize=None)
    def fib(n):
        count[0] += 1
        if n < 2:
            return n
        return fib(n-1) + fib(n-2)

    return fib, count

fib_calculation, count_list = fibonacci_memoized()
given_index = 7
result = fib_calculation(given_index)
print("Memoized recursive Fibonacci sequence solution:", result, "Execution:", count_list[0])

2. 增加输入合法性检查 #

添加对输入索引的校验，避免传入负数、非整数等非法值：

def fibonacci_memoized():
    cached = {}
    count = [0]

    def fib(n):
        if not isinstance(n, int) or n < 0:
            raise ValueError("索引必须是非负整数")
        count[0] += 1
        if n in cached:
            return cached[n]
        elif n < 2:
            cached[n] = n
            return n
        elif n >= 2:
            cached[n] = fib(n-1) + fib(n-2)
            return cached[n]

    return fib, count

3. 优化计数变量的实现 #

如果觉得用列表存储计数不够直观，可以使用自定义计数器类替代：

class Counter:
    def __init__(self):
        self.value = 0

def fibonacci_memoized():
    cached = {}
    count = Counter()

    def fib(n):
        count.value += 1
        if n in cached:
            return cached[n]
        elif n < 2:
            cached[n] = n
            return n
        elif n >= 2:
            cached[n] = fib(n-1) + fib(n-2)
            return cached[n]

    return fib, count

fib_calculation, counter = fibonacci_memoized()
given_index = 7
result = fib_calculation(given_index)
print("Memoized recursive Fibonacci sequence solution:", result, "Execution:", counter.value)

内容的提问来源于stack exchange，提问作者Faisal Khan