我无法理解自上而下的记忆化需要更大的表大小,因为自下而上和自上而下的方法都在 0(n) 时间复杂度内计算问题,无论他们在做什么,但是表的大小将保持不变,因为它们在表中存储 n 个斐波纳契项的结果,以防出现斐波那契问题 自上而下的情况下可能有堆栈溢出的风险,但表大小应该保持不变??
最佳答案
我认为这是因为您可以仅用 O(1) 空间实现自下而上的斐波那契数列。 在 python 伪代码中:
u=1
v=0
while n>0:
u,v = v,u+v
n=n-1
return v
关于algorithm - 自上而下的内存需要更大的表尺寸,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34090817/