递归,memoization和动态编程之间有什么区别？

Question

可能重复:
动态编程和记忆:自上而下与自下而上的方法

我已经阅读了很多文章,但似乎无法理解它.有时递归和动态编程看起来相同,而在其他时候,memoization和动态编程看起来很相似.有人可以向我解释有什么区别吗？

PS如果您可以使用针对同一问题的三种方法向我指出一些代码,那么它也会很有帮助.(例如Fibonacci系列问题,我认为我读过的每篇文章都使用了递归,但将其称为动态编程)

Answer 1

考虑计算斐波纳契数列:

纯递归:

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

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

导致指数的调用.

带有memoization/DP的递归:

int 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

好吧,递归+ memoization正是动态编程的一个特定"风格" :动态编程按照自上而下的方法.

更确切地说,没有专门使用递归的要求.任何分而治之的解决方案与memoization相结合的是自上而下的动态编程.(递归是分裂和征服的LIFO风格,而你也可以使用FIFO分治或任何其他类型的分治).

所以这样说更为正确

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

此外,从一个非常正式的角度来看,如果你为一个不产生重复部分解决方案的问题实施分而治之的解决方案(意味着在记忆中没有任何好处),那么你可以声称这种分而治之的解决方案是一个"动态编程"的退化例子.

但是,动态编程是一个更通用的概念.动态编程可以使用自下而上的方法,这与分而治之+记忆不同.

Answer 3

我相信你可以通过互联网找到详细的定义.这是我尝试简化的事情.

递归再次呼唤自己.

动态规划是一种解决具有特定结构(最佳子结构)的问题的方法,其中问题可以分解为与原始问题类似的子问题.显然,可以调用递归来解决DP.但这没有必要.可以在没有递归的情况下解决DP问题.

Memoization是一种优化依赖递归的DP算法的方法.重点不是要解决已经解决的子问题.您可以将其视为子问题解决方案的缓存.

Answer 4

它们是不同的概念.它们经常重叠,但它们是不同的.

只要函数直接或间接调用自身,就会发生递归.这是所有的了.

例:

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

动态编程是指在较小的子问题中使用解决方案以解决更大的问题.这是最容易递归实现的,因为您通常会根据递归函数来考虑这些解决方案.但是,迭代实现通常是首选,因为它需要更少的时间和内存.

Memoization用于防止递归DP实现比需要花费更多时间.大多数情况下,DP算法将使用相同的子问题来解决多个大问题.在递归实现中,这意味着我们将多次重新计算同一个东西.记忆意味着将这些子问题的结果保存到表中.当进入递归调用时,我们检查它的结果是否存在于表中:如果是,则返回它,否则,我们计算它,将其保存在表中,然后返回它.