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

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

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

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

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

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

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

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

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

下面是一个适合动态规划的例子，来自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.

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

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

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

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

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

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

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

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

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

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

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

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

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

动态规划

定义

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

关键理念

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

动态规划属性

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

下面是一个简单的python代码示例，用于递归、自顶向下、自底向上的斐波那契数列:

递归:O (2 n)

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

自上而下:O(n)高效的大输入

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

自底向上:O(n)为简单和小的输入大小

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))