动态规划和递归的区别

Question

动态规划和递归有什么区别？我在 geeksforgeeks tutorial point 和 Wikipedia 上浏览了很多文章，但在我看来两者都是一样的。

你能用斐波那契数列的例子解释一下动态规划和递归的区别吗？

Answer 1

计算斐波那契数列中的项非常容易，因为实际上您只需要记住fib(n-2)和fib(n-1)即可计算fib(n)。因为它是如此简单，任何算法都将变得非常简单，所以这个例子模糊了不同动态规划范式之间的细微差别。话虽这么说，你提到的维基百科页面对斐波那契有一个很好的解释：https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence

如果函数在执行过程中调用自身，则该函数被称为递归。

动态规划算法可以使用或不使用递归来实现。

动态规划的核心是利用以下两个事实来编写算法：

问题的解决方案可以分解为子问题的解决方案；
当问题 P 的最佳解决方案 S 被分解为解决方案 s1、s2、...子问题 p1、p2, ..., 然后s1, s2, ...都是各自子问题的最优解

请注意，这两个事实并非适用于所有问题。如果这两个事实适用于问题，则该问题仅适用于动态规划。

一个简单的例子是求从A点到B点的最短路径：如果从A点到B点的最短路径经过C点，那么从A点到C点和从C点到B点的两半由也是最短路径。

在大多数情况下，您可以进行递归调用来解决子问题。但是“天真的”递归方法很容易导致指数算法，因为“为了解决这个问题，我需要解决这两个（或更多）子问题”的级联可能会迅速增加你必须解决的问题数量解决。这是一个斐波那契的例子：

fib(5) = fib(4) + fib(3)
  fib(4) = fib(3) + fib(2)
    fib(3) = fib(2) + fib(1)
      fib(2) = fib(1) + fib(0)
        fib(1) = 1
        fib(0) = 0
      fib(1) = 1
    fib(2) = fib(1) + fib(0)
      fib(1) = 1
      fib(0) = 0
    fib(1) = 1
  fib(3) = fib(2) + fib(1)
    fib(2) = fib(1) + fib(0)
      fib(1) = 1
      fib(0) = 0
    fib(1) = 1

这里我们必须计算 16 个项才能找到 fib(5)。但请注意，总共只有 6 个不同的术语。当然，我们可以通过避免一次又一次地重复相同的计算来提高效率。

为避免这种情况，动态规划算法通常相当于用子问题的解决方案填充一个数组。一旦确定了子问题列表和数组，就没有太多动力去“自上而下”地进行递归调用，从最大的问题开始，然后依次将其分解为更小的子问题。相反，您可以从最微不足道的问题开始“自下而上”地填充数组，然后使用这些问题来解决更复杂的问题，直到您解决了您最初想要解决的问题。对于斐波那契数列，您可能会得到以下代码：

int f[n+1];
f[0] = 0;
f[1] = 1;
for (int k = 2; k <= n; k++)
  f[k] = f[k-2] + f[k-1];
return f[n];

然而，对于斐波那契数列，您只需要随时记住最后两项，而不是用从 fib(0) 到 fib(n) 的所有项填充一个完整的数组，您可以简单地保留两个变量（或一个大小为 2 的数组）和前两个结果。可以说这仍然是动态规划，尽管它最终只是一个按顺序计算序列项的循环并且很难看到任何关于它的“动态”。

动态规划和递归的区别

Difference between dynamic programming and recursion

recursion

dynamic-programming

fibonacci