什么是递归，记忆化和动态编程之间的区别？ [重复](What's the differe

可能重复：
动态规划和记忆化：自上而下VS自下而上的方法

我已经经历了很多的这个文章走了，但似乎无法理解它。有时，递归和动态规划看起来是一样的，在别人记忆化和动态编程看起来很相像。能向我解释的人有什么区别？

PS这也将是有益的，如果你能使用同样的问题的三种方法指向我一些代码。（如斐波纳契数列的问题，我觉得每一篇文章我读了使用递归，但把它称为动态编程）

Answer 1:

考虑计算斐波那契序列：

纯递归：

int fib(int x)
{
    if (x < 2)
        return 1;

    return fib(x-1) + fib(x-2);
}

结果在通话指数数。

递归与记忆化/ DP：

void fib(int x)
{
    static vector<int> cache(N, -1);

    int& result = cache[x];

    if (result == -1)
    {
        if (x < 2)
            result = 1;
        else
            result = fib(x-1) + fib(x-2);
    }

    return result;
}

现在我们有了第一次通话的直线号码，此后不断。

上述方法称为“懒”。我们计算的早期条款首次将要求他们提供。

下面也被认为DP，但没有递归：

int fibresult[N];

void setup_fib()
{
    fibresult[0] = 1;
    fibresult[1] = 1;
    for (int i = 2; i < N; i++)
       fibresult[i] = fibresult[i-1] + fibresult[i-2];
}

int fib(int x) { return fibresult[x]; }

这种方式可被描述为“急切”，“预先缓存”或“迭代”。它更快的整体，但我们必须手动找出子问题需要在计算顺序。这是很容易的斐波那契数，但对于较复杂的DP问题就更困难了，所以我们退回到懒洋洋的递归方法，如果它是快足够。

还有以下既不是递归也不DP：

int fib(int x)
{
    int a = 1;
    int b = 1;
    for (int i = 2; i < x; i++)
    {
        a = a + b;
        swap(a,b);
    }
    return b;
}

它采用恒定的空间和线性时间。

还我将提到为完整起见存在用于斐波纳契一个封闭的形式使用阴递归也不DP，使我们能够使用基于黄金比例的数学公式中恒定的时间计算斐波纳契术语：

http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-form/

Answer 2:

那么， 递归+记忆化恰恰是动态规划的一个特定的“味”：按照自上而下的方法动态规划。

更确切地说，没有requrement专门使用递归。任何分＆治之溶液与缓存结合是自上而下的动态规划。（递归是分而治之的LIFO风味，同时也可以使用FIFO分而治之或任何其他类型的鸿沟与征服的）。

因此，它是更正确地说，

divide & conquer + memoization == top-down dynamic programming

另外，从一个非常正式的点，如果实施不产生重复的部分解决问题的分而治之的解决方案（这意味着有一个在记忆化没有好处），那么你就可以声称这道鸿沟和征服的解决方案是一个“动态编程”的简并的例子。

然而， 动态编程是一个比较笼统的概念。动态编程可以使用自底向上的方法，它是从除法＆治+记忆化不同。

Answer 3:

我敢肯定，你可以在网上找到详细的定义。这是我试图把事情简单化。

递归再次调用本身。

动态规划是解决表现出一个特定的结构（最佳子结构），其中的一个问题可被分解成其类似于原来的问题的子问题的问题的一种方式。显然，一个可以调用递归解决DP。但它是没有必要的。一个能解决一个DP没有递归。

记忆化是优化依靠递归算法DP的方式。问题的关键是不要再解决问题，子已经已经解决了。你可以把它看作子问题的解决方案的缓存。

Answer 4:

他们是不同的概念。他们很经常重叠，但它们是不同的。

递归发生每当一个函数调用自身，直接或间接的影响。这是所有的了。

例：

a -> call a
a -> call b, b -> call c, c -> call a

动态规划是，当你为了解决一个更大的问题使用更小的子问题的解决方案。这是最简单的，因为你通常在递归函数的角度来考虑这样的解决方案，以实现递归。一个迭代实现通常是虽然首选，因为它需要较少的时间和内存。

记忆化是用来防止递归DP实现从以比需要更多的时间。大多数时候，一个DP算法将使用相同的子问题解决多个大问题。在递归实现，这意味着我们将同样的事情多次重新计算。记忆化意味着这些子问题的结果保存到一个表。进入一个递归调用的时候，我们检查，如果其结果的表存在：如果是，我们返回，如果不是，我们计算它，将它保存在表中，然后返回。