记忆是指存储函数调用之前的结果(给定相同的输入，真正的函数总是返回相同的结果)。在存储结果之前，算法的复杂性并没有什么不同。

递归是函数调用自身的方法，通常使用较小的数据集。由于大多数递归函数可以转换为类似的迭代函数，这对算法复杂性也没有影响。

动态规划是解决较容易解决的子问题，并由此建立答案的过程。大多数DP算法将处于贪婪算法(如果存在的话)和指数算法(枚举所有可能性并找到最佳的一个)之间的运行时间。

DP算法可以用递归来实现，但它们不必这样做。 DP算法不能通过记忆来加速，因为每个子问题只被解决(或“solve”函数被调用)一次。

记忆是指存储函数调用之前的结果(给定相同的输入，真正的函数总是返回相同的结果)。在存储结果之前，算法的复杂性并没有什么不同。

递归是函数调用自身的方法，通常使用较小的数据集。由于大多数递归函数可以转换为类似的迭代函数，这对算法复杂性也没有影响。

动态规划是解决较容易解决的子问题，并由此建立答案的过程。大多数DP算法将处于贪婪算法(如果存在的话)和指数算法(枚举所有可能性并找到最佳的一个)之间的运行时间。

DP算法可以用递归来实现，但它们不必这样做。 DP算法不能通过记忆来加速，因为每个子问题只被解决(或“solve”函数被调用)一次。

我对动态规划(一种针对特定类型问题的强大算法)也非常陌生。

简单地说，只需将动态规划视为使用前面知识的递归方法

以前的知识在这里是最重要的，跟踪你已经有的子问题的解决方案。

下面是来自维基百科的dp最基本的例子

求斐波那契数列

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

让我们用n = 5来分解函数调用

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

特别地，fib(2)从零开始计算了三次。在较大的示例中，需要重新计算fib(或子问题)的更多值，从而形成指数时间算法。

现在，让我们尝试将我们已经找到的值存储在一个数据结构(比如Map)中

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

这里我们将子问题的解决方案保存在地图中，如果我们还没有的话。这种我们已经计算过的保存值的技术被称为记忆化。

最后，对于一个问题，首先尝试找到状态(可能的子问题，并尝试考虑更好的递归方法，以便将以前的子问题的解决方案用于进一步的子问题)。

动态规划是求解具有重叠子问题的问题的一种技术。 动态规划算法只解决每个子问题一次，然后 将答案保存在一个表(数组)中。 避免每次遇到子问题时重新计算答案的工作。 动态规划的基本思想是: 避免计算相同的东西两次，通常是通过保留子问题的已知结果表。

动态规划算法开发的七个步骤如下:

建立递归属性，给出问题实例的解决方案。 根据递归特性开发递归算法 看看同一个问题的实例是否在递归调用中被一次又一次地解决 开发一个记忆递归算法 查看在内存中存储数据的模式 将记忆递归算法转化为迭代算法 根据需要使用存储对迭代算法进行优化(存储优化)

动态规划的关键是“重叠子问题”和“最优子结构”。问题的这些性质意味着最优解是由它的子问题的最优解组成的。例如，最短路径问题具有最优子结构。从A到C的最短路径是从A到某个节点B的最短路径，后面跟着从该节点B到C的最短路径。

更详细地说，要解决最短路径问题，您将:

求出从起始节点到触及它的每个节点的距离(比如从A到B和C) 求出这些节点到与其接触的节点的距离(从B到D和E，以及从C到E和F) 我们现在知道了从A到E的最短路径:它是我们访问过的某个节点x的A-x和x-E的最短和(B或C) 重复这个过程，直到到达最终的目标节点

因为我们是自下而上地工作，所以当需要使用这些子问题时，我们已经通过记忆它们得到了它们的解决方案。

记住，动态规划问题必须有重叠的子问题和最优的子结构。斐波那契数列的生成不是一个动态规划问题;它利用记忆，因为它有重叠的子问题，但它没有最优的子结构(因为不涉及优化问题)。

动态规划是指使用过去的知识来更容易地解决未来的问题。

一个很好的例子是求解n=1,000,002的斐波那契数列。

这将是一个非常漫长的过程，但是如果我给出n=1,000,000和n=1,000,001的结果呢?突然之间，问题变得更容易控制了。

动态规划在字符串问题中被大量使用，例如字符串编辑问题。您解决问题的一个子集，然后使用该信息来解决更困难的原始问题。

使用动态编程，通常将结果存储在某种表中。当你需要一个问题的答案时，你可以参考表格，看看你是否已经知道它是什么。如果没有，你可以利用表格中的数据为自己找到答案提供一个垫脚石。

Cormen算法书中有一章是关于动态规划的。而且它在谷歌Books上是免费的!点击这里查看。