动态规划的迭代解法能否使用记忆化技术？

Question

4

例如，当使用递归解决斐波那契数列时，可以使用记忆化技术。但是在使用栈和while循环迭代地解决斐波那契数列时，是否也能利用记忆化技术呢？

- Gabriel John Rodriguez

1

@Dukeling，在迭代解决方案中有什么需要记忆化的吗？没有。你已经在一个存储器上向前工作，重复使用存储的值是动态规划方法的意义所在。在动态（迭代）设置中谈论记忆化是毫无意义的。 - Will Ness

@WillNess 如果你以功能上相同的方式迭代地实现递归解决方案，如果不重用先前计算的值，它将需要指数时间。但当然，在斐波那契数列中这样做是不必要的，因为有一个更简单的迭代解决方案。迭代实现并不只有一种方法。 - Bernhard Barker

@WillNess 递归记忆化可以与自顶向下的解决方案配合使用。你是说迭代解决方案必须自下而上工作才能获得相同的优势吗？有没有一种方法可以自上而下地迭代工作，同时仍然获得记忆化的好处？ - Gabriel John Rodriguez

@Dukeling，“迭代”已经意味着我正在计数，使用较小的值来产生下一个值。如果我没有使用先前生成的值，那么这就不是一种迭代解决方案，对吗？ - Will Ness

@WillNess 我认为任何循环（for/while）都是迭代的（包括使用栈完全模拟递归的 while 循环），如果你不同意，那么我想我们就有不同的定义。 - Bernhard Barker

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Prune · Answer 1

当然...从基本情况F(0)和F(1)开始，计算数值。将它们全部保存在一个数组中，由函数下标进行索引。当您得到一个大于当前数组范围的输入参数时，计算更多数值。当您得到一个在当前界限内的参数时，只需从数组中返回该值即可。