什么是动态规划，它与递归有何不同？

Question

我无法理解动态编程如何改进简单递归。我知道这两种技术都涉及将问题分解为子问题，但是动态编程究竟如何使解决这些子问题更有效？有人可以澄清记忆化的概念以及它如何防止动态规划中的冗余计算吗？

我研究了递归算法的示例并研究了动态编程概念，但动态编程相对于简单递归所提供的改进尚不清楚。我期望了解动态编程如何避免冗余计算并通过记忆或制表等技术实现效率。

Answer 1

当您遇到“重叠子问题”时，动态规划的威力就显而易见了。以计算第 n 个

斐波那契数为例。

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)

无需记忆或制表，计算

f(n)

很快就会导致一遍又一遍地重新计算相同的子问题。

通过记忆，您可以重复使用之前已经计算过的实例的结果。

通过使用记忆化，我们将

O(2^n) 解决方案转变为更加高效的

O(n)

 解决方案。由于本例中存在许多重叠的子问题，因此这种转换是可能的。这并不总是正确的。你必须分析你手头的问题来决定动态编程是否是一个好的解决方案。