63

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

我已经阅读了很多关于此的文章，但似乎无法理解。有时递归和动态编程看起来一样，而在其他时候，记忆化和动态编程看起来很相似。有人可以向我解释有什么区别吗？

PS 如果您可以在同一问题上使用三种方法向我指出一些代码，这也会很有帮助。（例如斐波那契数列问题，我认为我阅读的每篇文章都使用了递归，但将其称为动态规划）

4

5 回答 5

72

考虑计算斐波那契数列：

纯递归：

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

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

导致调用次数呈指数增长。

带有记忆/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/

于 2012-08-26T22:18:04.910 回答
42

好吧，递归+记忆正是动态编程的一种特殊“风格” ：按照自顶向下的方法进行动态编程。

更准确地说，不需要专门使用递归。任何与记忆相结合的分治解决方案都是自上而下的动态编程。（递归是分治法的 LIFO 风格，而您也可以使用 FIFO 分治法或任何其他类型的分治法）。

所以更正确的说法是

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

此外，从非常正式的角度来看，如果您为不产生重复部分解决方案的问题实施分治解决方案（这意味着记忆化没有好处），那么您可以声称这种分治解决方案是“动态规划”的退化示例。

然而，动态规划是一个更普遍的概念。动态编程可以使用自下而上的方法，这与分治法+记忆法不同。

于 2012-08-26T21:54:45.007 回答
19

我相信您可以在互联网上找到详细的定义。这是我简化事情的尝试。

递归再次调用自己。

动态规划是一种解决具有特定结构（最佳子结构）的问题的方法，其中问题可以分解为与原始问题相似的子问题。显然，可以调用递归来解决 DP。但这不是必需的。无需递归即可解决 DP。

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

于 2012-08-26T20:56:07.847 回答
9

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

每当函数直接或间接调用自身时，就会发生递归。这就是全部。

例子：

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

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

Memoization is used to prevent recursive DP implementation from taking a lot more time than needed. Most times, a DP algorithm will use the same subproblem in solving multiple large problems. In a recursive implementation, this means we will recompute the same thing multiple times. Memoization implies saving the results of these subproblems into a table. When entering a recursive call, we check if its result exists in the table: if yes, we return it, if not, we compute it, save it in the table, and then return it.

于 2012-08-26T23:09:24.587 回答
-5

递归与记忆和动态编程绝对无关；这是一个完全独立的概念。

否则，这是一个重复的问题：动态编程和记忆：自下而上与自上而下的方法

于 2012-08-26T20:46:02.723 回答