什么是dynamic编程？

什么是dynamic编程 ？

与recursion，记忆等有什么不同？

我已经阅读了维基百科的文章 ，但是我还是不太明白。

Answer 1

dynamic规划就是当你使用过去的知识来解决未来的问题时更容易。

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

这将是一个非常漫长的过程，但是如果我给你n = 1,000,000和n = 1,000,001的结果呢？ 突然之间，问题变得更加易于pipe理。

dynamic编程在string问题中被使用了很多，比如string编辑问题。 您解决问题的一个子集，然后使用这些信息来解决更难的原始问题。

通过dynamic编程，您可以将结果存储在某种表格中。 当你需要问题的答案时，你引用表格，看看你是否已经知道它是什么。 如果不是的话，你可以使用表格中的数据为自己find答案的垫脚石。

Cormenalgorithm书有一个关于dynamic编程的伟大篇章。 而且在Google图书上免费！ 看看这里。

Answer 2

dynamic规划是一种用于避免在recursionalgorithm中计算多个时间相同的子问题的技术。

我们来看一个斐波那契数的简单例子：find第n ^个斐波那契数

F _n = F _n-1 + F _n-2且F ₀ = 0，F ₁ = 1

recursion

明显的做法是recursion的：

def fibonacci(n): if n == 0: return 0 if n == 1: return 1 return fibonacci(n - 1) + fibonacci(n - 2) 

dynamic编程

• 自上而下 – 纪事

recursion做了很多不必要的计算，因为给定的斐波那契数将被多次计算。 一个简单的方法来改善这是caching结果：

 cache = {} def fibonacci(n): if n == 0: return 0 if n == 1: return 1 if n in cache: return cache[n] cache[n] = fibonacci(n - 1) + fibonacci(n - 2) return cache[n] 

• 自下而上

一个更好的方法是通过以正确的顺序评估结果来摆脱recursion：

 cache = {} def fibonacci(n): cache[0] = 0 cache[1] = 1 for i in range(2, n + 1): cache[i] = cache[i - 1] + cache[i - 2] return cache[n] 

我们甚至可以使用恒定的空间，只存储必要的部分结果：

 def fibonacci(n): fi_minus_2 = 0 fi_minus_1 = 1 for i in range(2, n + 1): fi = fi_minus_1 + fi_minus_2 fi_minus_1, fi_minus_2 = fi, fi_minus_1 return fi 

• 如何应用dynamic编程？

  1. find问题的recursion。
  2. 自上而下：将每个子问题的答案存储在表中以避免重新计算它们。
  3. 自下而上：find正确的顺序来评估结果，以便在需要时提供部分结果。

dynamic编程通常适用于具有固有从左到右顺序的问题，如string，树或整数序列。 如果简单的recursionalgorithm不能多次计算相同的子问题，dynamic编程将无济于事。

我收集了一些问题来帮助理解逻辑： https ： //github.com/tristanguigue/dynamic-programing

Answer 3

这是我在类似的主题回答

从…开始

• 维基百科有关dynamic编程的文章
• 我build议你在topcoder阅读这篇文章
• ch6关于algorithm中的dynamic规划 （Vazirani）
• algorithmdevise手册中的dynamic编程章节
• algorithm经典书籍dynamic规划篇（algorithm导论 ）

如果你想testing自己，我对网上评委的select是

• Uvadynamic编程问题
• Timusdynamic编程问题
• Spojdynamic编程问题
• TopCoderdynamic编程问题

而且当然

• 看看algorithmist dynamic编程的类别

你也可以检查好的大学algorithm课程

• Aduni（algorithm）
• 麻省理工学院（介绍algorithm（第15章））

毕竟，如果你不能解决问题，那么在这里存在很多algorithm成瘾者

Answer 4

记忆是指当你存储一个函数调用的前一个结果（一个真实的函数总是返回相同的东西，给定相同的input）。 在存储结果之前，algorithm的复杂性没有任何区别。

recursion是调用自己的函数的方法，通常使用较小的数据集。 由于大多数recursion函数可以转换为类似的迭代函数，所以这对algorithm的复杂性也没有什么不同。

dynamic规划是解决更容易解决的子问题，并从中提出答案的过程。 大多数DPalgorithm将处于Greedyalgorithm（如果存在的话）和指数（列举所有可能性并find最好的algorithm）之间的运行时间。

• DPalgorithm可以用recursion实现，但不一定是。
• DPalgorithm不能通过记忆加速，因为每个子问题只能解决一次（或称为“解决”函数）。

Answer 5

这是对algorithm的优化，可以缩短运行时间。

虽然贪婪algorithm通常被称为天真的 ，因为它可能运行多个相同的数据集，dynamic规划通过深入了解必须存储的部分结果来避免这个陷阱，以帮助构build最终的解决scheme。

一个简单的例子是遍历一个树或一个graphics，只能通过解决scheme的贡献节点，或者到目前为止你find的解决scheme放到表中，这样你就可以避免遍历同一个节点。

下面是一个适合dynamic编程的例子，从UVA的在线评判： Edit Steps Ladder。

我将从“编程挑战”这本书中快速介绍这个问题分析的重要部分，我build议你检查一下。

仔细看看这个问题，如果我们定义一个成本函数来告诉我们两个string有多远，我们有两个考虑三种自然types的变化：

replace – 将单个字符从模式“s”更改为文本“t”中的不同字符，例如将“shot”更改为“spot”。

插入 – 将单个字符插入到模式“s”中以帮助匹配文本“t”，例如将“ago”更改为“agog”。

删除 – 从模式“s”中删除单个字符以帮助匹配文本“t”，例如将“hour”更改为“our”。

当我们设置每个操作花费一个步骤时，我们定义两个string之间的编辑距离。 那么我们如何计算呢？

我们可以使用这样的观察来定义一个recursionalgorithm，即string中的最后一个字符必须是匹配，replace，插入或删除的。 在上次编辑操作中剔除字符会使一对操作留下一对较小的string。 设i和j分别是和t的相关前缀的最后一个字符。 在最后的操作之后有三对较短的string，对应于匹配/replace，插入或删除之后的string。 如果我们知道编辑三对较小string的成本，我们可以决定哪个选项导致最佳解决scheme，并相应地select该选项。 我们可以通过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 ); > > } 

这个algorithm是正确的，但也是不可能的。

在我们的计算机上运行，​​比较两个11字符的string需要花费几秒钟，计算消失在永远不再永远不会再着陆。

为什么algorithm这么慢？ 它需要指数的时间，因为它重复计算一次又一次的值。 在string中的每一个位置，recursion都有三种方式，意味着它以至less3 ^ n的速度增长 – 实际上，甚至更快，因为大多数调用只减less两个索引中的一个，而不是两个。

那么我们怎样才能使algorithm实用？ 重要的观察是，这些recursion调用中的大部分都是计算之前已经计算好的东西。 我们怎么知道？ 那么只能有| s | ·| t | 可能的唯一recursion调用，因为只有许多不同的（i，j）对用作recursion调用的参数。

通过将这些（i，j）对中的每一个的值存储在一个表中，我们可以避免重新计算它们，只是根据需要查找它们。

该表是一个二维matrixm，其中每个| s |·| t | 单元格包含了这个子问题的最优解的代价，以及解释我们如何到达这个位置的父指针：

  typedef struct { int cost; /* cost of reaching this cell */ int parent; /* parent cell */ } cell; cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */ 

dynamic编程版本与recursion版本有三个不同之处。

首先，它使用表查找而不是recursion调用来获取中间值。

**其次，**更新每个单元格的父字段，这将使我们能够稍后重新编辑序列。

**第三，**第三，它使用一个更一般的目标cell（）函数，而不是仅返回m [| s |] [| t |] .cost。 这将使我们能够将这个例程应用于更广泛的问题。

在这里，对于收集最优化的部分结果所花费的非常特别的分析，是解决scheme是“dynamic的”解决scheme。

这是对相同问题的另一种完整解决scheme。 即使它的执行不同，它也是一个“dynamic”的。 我build议你通过提交给UVA的在线评审来检查解决scheme的有效性。 我发现这样一个重大的问题是如此有效地处理的惊人之处。

Answer 6

dynamic规划的关键是“重叠子问题”和“最优子结构”。 问题的这些性质意味着最佳解决scheme是由其子问题的最佳解决scheme组成的。 例如，最短path问题展现出最佳的子结构。 从A到C的最短path是从A到某个节点B的最短path，接着是从该节点B到C的最短path。

更详细地说，要解决最短path问题，您将：

• find从起始节点到每个接触节点的距离（比如从A到B和C）
• 找出从这些节点到接触节点的距离（从B到D和E，从C到E和F）
• 我们现在知道从A到E的最短path：它是我们访问过的某个节点x（B或C）的Ax和xE的最短和，
• 重复这个过程，直到我们到达最终的目标节点

因为我们正在自下而上的工作，所以我们已经有了解决这些子问题的方法。

请记住，dynamic规划问题必须同时存在重叠的子问题和最佳的子结构。 生成斐波那契数列不是一个dynamic规划问题; 它利用memoization，因为它有重叠的子问题，但它没有最佳的子结构（因为没有涉及优化问题）。

Answer 7

dynamic编程

定义

dynamic规划（DP）是解决重叠子问题的一般algorithmdevise技术。 这种技术是由美国math家“理查德·贝尔曼”在20世纪50年代发明的。

关键的想法

关键的想法是保存重叠较小的子问题的答案以避免重新计算。

dynamic编程属性

• 使用较小实例的解决scheme解决实例。
• 小型实例的解决scheme可能需要多次，因此将其结果存储在一个表中。
• 因此每个较小的实例只解决一次。
• 额外的空间用于节省时间。

Answer 8

这里是来自CMU的Michael A. Trick的一篇教程，我发现它特别有用：

http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

当然，除了别人推荐的所有资源（所有其他资源，特别是CLR和Kleinberg，Tardos都非常好！）之外。

我喜欢这个教程的原因是因为它逐渐引入了先进的概念。 这是有点古老的材料，但是这是在这里介绍的资源清单的一个很好的补充。

另外请查看Steven Skiena的主页和dynamic规划讲座： http : //www.cs.sunysb.edu/~algorith/video-lectures/

~algorith/video-lectures/1997/lecture12.pdf

Answer 9

我对dynamic编程也很新颖（针对特定types问题的强大algorithm）

用最简单的话来说，就是把dynamic规划看作是使用以前知识的recursion方法

以前的知识是最重要的，跟踪你已经有的子问题的解决scheme。

考虑一下，这是维基百科最基本的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）从头开始计算三次。 在更大的例子中，重新计算更多的纤维值或子问题，从而形成指数时间algorithm。

现在，让我们通过将我们已经find的值存储在一个数据结构（比如Map）中来尝试它

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

如果我们没有，我们在这里保存子问题的解决scheme。 这种保存我们已经计算出来的价值的技术被称为Memoization。

最后，对于一个问题，首先尝试find状态（可能的子问题，并尝试考虑更好的recursion方法，以便可以使用以前的子问题的解决scheme进一步的）。

Answer 10

简而言之，recursion记忆和dynamic编程之间的区别

dynamic编程如名称所示，使用之前的计算值dynamic构build下一个新的解决scheme

在哪里应用dynamic规划：如果您的解决scheme是基于最佳子结构和重叠子问题，那么在这种情况下使用先前计算的值将是有用的，因此您不必重新计算它。 这是自下而上的方法。 假设你需要计算fib（n），那么你需要做的就是将前面计算的fib（n-1）和fib（n-2）

recursion：基本上把你的问题细分成更小的部分来轻松地解决它，但记住，如果在其他recursion调用中先前计算的值相同，则不会避免重新计算。

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