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

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

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

下面是来自维基百科的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]

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

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

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

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

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

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

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

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

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

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

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

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

简而言之，就是递归记忆和动态规划的区别

顾名思义，动态规划是使用前面的计算值动态地构造下一个新的解决方案

在哪里应用动态规划:如果你的解决方案是基于最优子结构和重叠子问题，那么在这种情况下，使用之前的计算值将是有用的，这样你就不必重新计算它。这是一种自下而上的方法。假设你需要计算fib(n)在这种情况下，你所需要做的就是将之前计算的fib(n-1)和fib(n-2)的值相加

递归:基本上将你的问题细分为更小的部分，以轻松解决它，但请记住，如果我们在其他递归调用中有相同的值，它不会避免重新计算。

记忆:基本上将旧的计算递归值存储在表中被称为记忆，这将避免重新计算，如果它已经被以前的一些调用计算过，因此任何值都将计算一次。因此，在计算之前，我们检查这个值是否已经计算过，如果已经计算过，那么我们从表中返回相同的值，而不是重新计算。这也是一种自上而下的方法

这是对算法的优化，可以减少运行时间。

虽然贪婪算法通常被称为朴素算法，因为它可能在同一组数据上运行多次，但动态规划通过对必须存储的部分结果的更深入理解来避免这个陷阱，以帮助构建最终解决方案。

一个简单的例子是只遍历树或图中对解决方案有贡献的节点，或者将迄今为止找到的解决方案放入表中，这样就可以避免反复遍历相同的节点。

下面是一个适合动态规划的例子，来自UVA的在线评委:Edit Steps Ladder。

我将简要介绍这个问题分析的重要部分，摘自《编程挑战》一书，我建议你去看看。

Take a good look at that problem, if we define a cost function telling us how far appart two strings are, we have two consider the three natural types of changes: Substitution - change a single character from pattern "s" to a different character in text "t", such as changing "shot" to "spot". Insertion - insert a single character into pattern "s" to help it match text "t", such as changing "ago" to "agog". Deletion - delete a single character from pattern "s" to help it match text "t", such as changing "hour" to "our". When we set each of this operations to cost one step we define the edit distance between two strings. So how do we compute it? We can define a recursive algorithm using the observation that the last character in the string must be either matched, substituted, inserted or deleted. Chopping off the characters in the last edit operation leaves a pair operation leaves a pair of smaller strings. Let i and j be the last character of the relevant prefix of and t, respectively. there are three pairs of shorter strings after the last operation, corresponding to the string after a match/substitution, insertion or deletion. If we knew the cost of editing the three pairs of smaller strings, we could decide which option leads to the best solution and choose that option accordingly. We can learn this cost, through the awesome thing that's recursion: #define MATCH 0 /* enumerated type symbol for match */ #define INSERT 1 /* enumerated type symbol for insert */ #define DELETE 2 /* enumerated type symbol for delete */ int string_compare(char *s, char *t, int i, int j) { int k; /* counter */ int opt[3]; /* cost of the three options */ int lowest_cost; /* lowest cost */ if (i == 0) return(j * indel(’ ’)); if (j == 0) return(i * indel(’ ’)); opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]); opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]); opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]); lowest_cost = opt[MATCH]; for (k=INSERT; k<=DELETE; k++) if (opt[k] < lowest_cost) lowest_cost = opt[k]; return( lowest_cost ); } This algorithm is correct, but is also impossibly slow. Running on our computer, it takes several seconds to compare two 11-character strings, and the computation disappears into never-never land on anything longer. Why is the algorithm so slow? It takes exponential time because it recomputes values again and again and again. At every position in the string, the recursion branches three ways, meaning it grows at a rate of at least 3^n – indeed, even faster since most of the calls reduce only one of the two indices, not both of them. So how can we make the algorithm practical? The important observation is that most of these recursive calls are computing things that have already been computed before. How do we know? Well, there can only be |s| · |t| possible unique recursive calls, since there are only that many distinct (i, j) pairs to serve as the parameters of recursive calls. By storing the values for each of these (i, j) pairs in a table, we can avoid recomputing them and just look them up as needed. The table is a two-dimensional matrix m where each of the |s|·|t| cells contains the cost of the optimal solution of this subproblem, as well as a parent pointer explaining how we got to this location: typedef struct { int cost; /* cost of reaching this cell */ int parent; /* parent cell */ } cell; cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */ The dynamic programming version has three differences from the recursive version. First, it gets its intermediate values using table lookup instead of recursive calls. **Second,**it updates the parent field of each cell, which will enable us to reconstruct the edit sequence later. **Third,**Third, it is instrumented using a more general goal cell() function instead of just returning m[|s|][|t|].cost. This will enable us to apply this routine to a wider class of problems.

这里，对收集最优部分结果所需要的内容进行了非常具体的分析，是什么使解决方案成为“动态”解决方案。

这是同样问题的另一个完整的解决方案。它也是一个“动态的”游戏，尽管其执行方式有所不同。我建议你把它提交给弗吉尼亚大学的在线评委，看看这个解决方案有多有效。如此沉重的问题竟能如此有效地解决，我感到惊奇。

动态规划

定义

动态规划(DP)是求解问题的一种通用算法设计技术 带有重叠子问题的问题。这项技术是美国人发明的 数学家理查德·贝尔曼在20世纪50年代。

关键理念

其关键思想是保存重叠的小问题的答案，以避免重新计算。

动态规划属性

使用较小实例的解决方案求解实例。 较小实例的解决方案可能需要多次使用， 所以把结果存储在一个表中。 因此，每个较小的实例只解决一次。 额外的空间被用来节省时间。