动态规划：递归+记忆 vs 循环+列表

Question

@functools.lru_cache 的文档提供了一个使用缓存计算斐波那契数列以实现动态编程技术的示例：

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

我见过这种用于解决各种编程难题的方法。它是否具有与 'standard' 迭代动态规划方法相同的 time/space 复杂度，例如：

def fib(n):
    if n < 2:
        return n
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(2 , n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

此外，使用递归方法有什么缺点吗？

Answer 1

它应该具有与 memoization（自上而下）那种动态规划相同的复杂性。

具有逐步 table 填充的迭代方法（自下而上的动态规划）可能具有略微不同的复杂性，因为记忆只记住参数集，需要构建最终解决方案

这种差异对于斐波那契或阶乘示例并不重要，但对于具有稀疏子问题的任务可能会发生 table（当很难预测稍后将使用哪些条目时）

Answer 2

下面比较了你展示的功能。一般来说，这些观察不一定适用于任何计算斐波那契数的递归或迭代方法，但仅适用于您在问题中显示的实现。

时间复杂度：

第一次通话

递归方法：O(n)
迭代方法：O(n)

后续调用

递归方法：O(1)
迭代方法：O(n)

常数因子

常数因子可能完全不同。很可能（第一次调用）迭代方法比递归方法更快，即使两者都是 O(n)。这只是一个猜测，根据我的经验（不是实际测试）列表索引比调用函数快得多。

内存复杂度：

两者都需要 O(n) 的额外内存，但是递归方法将保留内存（因此它是永久分配的），而迭代方法将在函数完成后释放内存。

其他差异

Python的递归极限。当时间变得太大并且缓存未被填充时，递归方法将由于该限制而失败，例如 fib(500)。列表索引没有这样的限制（除非你运行内存不足）。

动态规划：递归+记忆 vs 循环+列表

Dynamic programming: recursion+memoization vs loop+list

python

recursion

memoization

dynamic-programming