什么是递归，记忆化和放大器之间的差异;动态规划？ [英] What's the difference between recursion, memoization & dynamic programming?

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-top-down-vs-bottom-up-approaches">Dynamic编程和记忆化：由上而下VS由下而上的办法

我已经经历了很多关于这条走了，但似乎无法理解它。有时，递归和动态规划看起来是一样的，有时则记忆化和放大器;动态规划看起来很相像。可有人向我解释什么区别？

I have gone through a lot of articles on this but can't seem to make sense of it. At times recursion and dynamic programming looks the same and at others memoization & dynamic programming look alike. Can someone explain to me what's the difference?

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

P.S. It will also be helpful if you could point me to some code using the three approaches on the same problem. (e.g. the Fibonacci series problem, I think every article I read used recursion but referred to it as dynamic programming)

推荐答案

考虑计算斐波纳契数列：

Consider calculating the fibonacci sequence:

纯递归：

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

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

的结果调用的指数数量。

results in exponential number of calls.

递归与记忆化/ DP：

Recursion with memoization/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;
}

现在我们有呼叫的第一次的线性数量，和恒定此后

Now we have linear number of calls the first time, and constant thereafter.

以上方法被称为懒人。我们计算的早期术语第一次被提出的要求。

The above method is called "lazy". We calculate the earlier terms the first time they are asked for.

下面也将被认为是DP，但无需递归：

The following would also be considered DP, but without recursion:

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]; }

此方式可被描述为急切，precaching或迭代。其更快的整体，但我们要手工计算出子问题需要计算的顺序，这是很容易斐波那契，但对于较复杂的DP问题就变得更难，所以我们倒回懒人递归的方法，如果速度快够了。

This way may be described as "eager", "precaching" or "iterative". Its faster overall but we have to manually figure out the order the subproblems need to be calculated in. This is easy for fibonacci, but for more complex DP problems it gets harder, and so we fall back to the lazy recursive method if it is fast enough.

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

Also the following is neither recursion nor 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;
}

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

It uses constant space and linear time.

另外，我会提到出于完整性的存在是一个封闭的形式斐波纳契使用幽冥递归也不DP，使我们能够使用基于黄金比例的数学公式在固定时间计算斐波纳契词：

Also I will mention for the sake of completeness there is a closed form for fibonacci that uses nether recursion nor DP that allows us to calculate in constant time the fibonacci term using a mathematic formula based on the golden ratio:

<一个href="http://www.dreamin$c$c.net/forums/topic/115550-fibonacci-closed-form/">http://www.dreamin$c$c.net/forums/topic/115550-fibonacci-closed-form/

这篇关于什么是递归，记忆化和放大器之间的差异;动态规划？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！