algorithm - 自上而下的内存需要更大的表尺寸

Question

我无法理解自上而下的记忆化需要更大的表大小，因为自下而上和自上而下的方法都在 0(n) 时间复杂度内计算问题，无论他们在做什么，但是表的大小将保持不变，因为它们在表中存储 n 个斐波纳契项的结果，以防出现斐波那契问题自上而下的情况下可能有堆栈溢出的风险，但表大小应该保持不变？？

Answer 1

我认为这是因为您可以仅用 O(1) 空间实现自下而上的斐波那契数列。在 python 伪代码中:

u=1
v=0
while n>0:
    u,v = v,u+v
    n=n-1
return v