algorithm - 每个递归算法都可以用动态规划改进吗？

Question

我是 CSc 本科一年级学生，希望参加有竞争力的编程。

递归涉及定义和解决子问题。据我了解，自上而下的动态规划 (dp) 涉及内存子问题的解决方案，以降低算法的时间复杂度。

是否可以使用top down dp 来提高every 子问题重叠的递归算法的效率？ dp 在哪里无法工作，我该如何识别？

Answer 1

简短的回答是:是的。

但是，也有一些限制。最明显的一个是递归调用必须重叠。 IE。在算法的执行过程中，必须使用相同的参数多次调用递归函数。这使您可以通过内存截断递归树。因此，您始终可以使用内存来减少调用次数。

但是，通话次数的减少是有代价的。您需要将结果存储在某处。下一个明显的约束是您需要有足够的内存。这带有一个不太明显的约束。内存访问总是需要一些时间。您首先需要找到存储结果的位置，然后甚至可能将其复制到某个位置。所以在某些情况下，让递归计算结果而不是从某个地方加载它可能会更快。但这是非常特定于实现的，甚至可能取决于操作系统和硬件设置。