相关问题：
动态编程和记忆：自上而下与自下而上的方法
我已经阅读了很多关于此的文章，但似乎无法理解它。有时递归和动态编程看起来相同，而有时记忆和动态编程看起来很相似。有人可以向我解释一下有什么区别吗？
附注如果您能给我指出一些使用三种方法解决同一问题的代码，也会很有帮助。 （例如斐波那契数列问题，我认为我读过的每一篇文章都使用了递归，但将其称为动态规划）
考虑计算斐波那契数列：
纯递归：
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，允许我们使用基于黄金比例的数学公式在恒定时间内计算斐波那契项：
https://www.geeksforgeeks.org/find-nth-fibonacci-number-using-golden-ratio/
嗯，递归+记忆正是动态规划的特定“风味”：按照自顶向下方法进行动态规划。
更准确地说，不需要专门使用recursion。任何与记忆相结合的分而治之的解决方案都是自上而下的动态规划。 （递归是 LIFO 风格的分治法，同时您也可以使用 FIFO 分治法或任何其他类型的分治法）。
所以这样说比较正确
divide & conquer + memoization == top-down dynamic programming
此外，从非常正式的角度来看，如果您为一个问题实现了分而治之的解决方案，并且不会生成重复的部分解决方案（这意味着记忆化没有任何好处），那么您可以声称这个分而治之的解决方案是“动态规划”的退化例子。
然而，动态规划是一个更普遍的概念。动态规划可以使用自下而上的方法，这与分而治之+记忆化不同。
我相信您可以在互联网上找到详细的定义。这是我尝试简化事情的尝试。
递归再次调用自身。
动态规划是一种解决具有特定结构（最优子结构）的问题的方法，其中问题可以分解为与原始问题类似的子问题。显然，我们可以调用递归来求解 DP。但这是没有必要的。无需递归即可解决 DP。
Memoization 是一种优化依赖于递归的 DP 算法的方法。重点不是再次解决已经解决的子问题。您可以将其视为子问题解决方案的缓存。
它们是不同的概念。它们经常重叠，但又不同。
只要函数直接或间接调用自身，就会发生递归。这就是全部。
示例：
a -> call a
a -> call b, b -> call c, c -> call a
动态规划是指使用较小子问题的解决方案来解决更大的问题。这是最容易递归实现的，因为您通常会根据递归函数来考虑此类解决方案。不过，迭代实现通常是首选，因为它需要更少的时间和内存。
Memoization 用于防止递归 DP 实现花费比需要更多的时间。大多数时候，DP 算法会使用相同的子问题来解决多个大问题。在递归实现中，这意味着我们将多次重新计算同一件事。记忆化意味着将这些子问题的结果保存到表中。当进入递归调用时，我们检查它的结果是否存在于表中：如果存在，我们返回它，如果不存在，我们计算它，将其保存在表中，然后返回它。
递归与记忆和动态规划完全无关；这是一个完全独立的概念。
否则，这是一个重复的问题：动态编程和记忆：自下而上与自上而下的方法