algorithm - 理解动态规划的好例子、文章、书籍

Question

我无法弄清楚动态编程的原理，我真的很想要它。DP很强大，可以解决这样的问题：

从数字的差异中获得尽可能低的总和

那么，您能否向我推荐一些可以解释什么是动态编程的好书或文章（最好是带有真实代码的示例）？我真的想要首先简单的例子，然后我会继续。

score 34 · Accepted Answer

动态规划是一种有用的算法类型，可用于通过将困难问题分解为更小的子问题来优化它们。通过存储和重用部分解决方案，它设法避免了使用贪心算法的陷阱。动态规划有两种，自下而上和自上而下。

为了使用动态规划来解决问题，该问题必须具有所谓的最优子结构的性质。这意味着，如果将问题分解为一系列子问题，并找到每个子问题的最优解，那么最终的解决方案将通过这些子问题的解来实现。没有这种结构的问题不能用动态规划来解决。

自顶向下

自上而下更好地称为memoization。这是存储过去计算的想法，以避免每次重新计算它们。

给定一个递归函数，说：

fib(n) = 0 if n = 0
         1 if n = 1
         fib(n - 1) + fib(n - 2) if n >= 2

我们可以很容易地从它的数学形式递归地写成：

function fib(n)
  if(n == 0 || n == 1)
    n
  else
    fib(n-1) + fib(n-2)

现在，任何已经编程一段时间或对算法效率了解一两件事的人都会告诉你，这是一个糟糕的想法。原因是，在每一步，您都必须重新计算 fib(i) 的值，其中 i 为 2..n-2。

一个更有效的例子是存储这些值，创建自上而下的动态规划算法。

m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
  if(m[n] does not exist)
    m[n] = fib(n-1) + fib(n-2)

通过这样做，我们最多计算一次 fib(i)。

自下而上

自下而上使用与自上而下相同的记忆技术。然而，不同之处在于自下而上使用称为重复的比较子问题来优化您的最终结果。

在大多数自下而上的动态规划问题中，您经常尝试最小化或最大化决策。在任何给定点，您都有两个（或更多）选项，您必须决定哪个更适合您要解决的问题。但是，这些决定是基于您之前做出的选择。

通过在每个点（每个子问题）做出最佳决策，您可以确保您的整体结果是最佳的。

这些问题中最困难的部分是找到解决问题的递归关系。

为了买一堆算法教科书，你打算抢劫一家有n件商品的商店。问题是你的小背包最多只能装W公斤。知道每件物品的重量 (w[i]) 和价值 (v[i])，您希望最大化您的赃物的价值，这些物品的总重量最多为 W。对于每件物品，您必须做出二元选择 -要么接受，要么离开它。

现在，您需要找出子问题是什么。作为一个非常聪明的小偷，您意识到给定项目的最大值 i 和最大重量 w 可以表示为 m[i, w]。此外，m[0, w]（最多 0 个权重 w）和 m[i,0]（i 个最大权重为 0 的项目）将始终等于 0 值。

所以，

m[i, w] = 0 if i = 0 or w = 0

戴上全面罩时，您会注意到，如果您的包里装满了尽可能多的重量，除非它的重量小于或等于您的最大重量和袋子的当前重量。您可能需要考虑的另一种情况是，它的重量是否小于或等于包中某件物品的重量，但价值更高。

 m[i, w] = 0 if i = 0 or w = 0
           m[i - 1, w] if w[i] > w
           max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w

这些是上面描述的递归关系。一旦有了这些关系，编写算法就非常容易（而且很短！）。

v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack
   
m[n, n] = array(int, int)
function knapsack
  for w=0..W
    m[0, w] = 0
  for i=1 to n
    m[i, 0] = 0
    for w=1..W
      if w[i] <= w
        if v[i] + m[i-1, w - w[i]] > m[i-1, w]
           m[i, w] = v[i] + m[i-1, w - w[i]]
        else
           m[i, w] = m[i-1, w]
      else
        m[i, w] = c[i-1, w]
  
  return m[n, n]

其他资源

示例问题

幸运的是，当涉及到竞争性编程时，动态编程已经变得非常流行。查看UVAJudge 上的 Dynamic Programming 以了解一些练习题，这些练习题将测试您实施和查找动态编程问题重现的能力。

score 10 · Accepted Answer

简而言之，动态规划是一种通过将复杂问题分解为更简单的步骤来解决复杂问题的方法，即逐步解决问题。

我希望这个链接至少会有所帮助。

score 6 · Accepted Answer

从...开始

那么关于动态编程的维基百科文章
我建议你在 topcoder 中阅读这篇文章
第 6 章关于算法中的动态规划（Vazirani）
算法设计手册中的动态规划章节
算法经典书籍中的动态规划章节（Introduction to Algorithms）

如果您想测试自己，我对在线评委的选择是

而且当然

看 algorithmist动态规划类

您还可以查看好的大学算法课程

毕竟，如果你不能解决问题，问 SO 这里存在许多算法上瘾者

score 5 · Accepted Answer

见下文

http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

并且上面的文章中有太多的示例和文章参考。

学习动态规划后，您可以通过解决UVA问题来提高您的技能，UVA讨论区中有一些 UVA 动态规划问题的列表

Wiki也有一个很好的简单示例。

编辑： 关于它的书籍算法，您可以使用：

Python 算法：掌握 Python 语言中的基本算法：在这本书中，您可以看到使用 DP 的实际工作。
Introduction to Algorithms：描述本书中算法的最简单的方法。

你也应该看看动态编程中的记忆。

score 4 · Accepted Answer

我认为代数动态规划值得一提。它是 DP 技术的一个非常鼓舞人心的介绍，并被广泛用于生物信息学界。此外，贝尔曼的最优性原理以非常容易理解的方式表述。

传统上，DP 是通过示例来教授的：算法是根据存储中间问题的解决方案的表条目之间的重复来转换的，从这个表中，整体解决方案是通过一些案例分析构建的。

ADP 组织 DP 算法，使问题分解为子问题和案例分析与预期的优化目标完全分离。这允许针对类似问题重用和组合 DP 算法的不同部分。

ADP算法中有三个松散耦合的部分：

建立搜索空间（用树语法表示）；
对搜索空间的每个元素进行评分；
选择搜索空间中我们感兴趣的那些元素的目标函数。

然后所有这些部分自动融合在一起，产生有效的算法。

score 3 · Accepted Answer

这篇 USACO 文章是了解 DP 基础知识以及它如何提供巨大加速的良好起点。然后看看这篇 TopCoder 文章，它也涵盖了基础知识，但写得不是很好。CMU的这个教程也很不错。一旦你理解了这一点，你就需要跳到 2D DP 来解决你提到的问题。通读这篇 Topcoder 文章，直至并包括苹果问题（标记为中间）。

您可能还会发现观看此 MIT 视频讲座很有用，具体取决于您从视频中学到的东西。

另请注意，在成功掌握 DP 之前，您需要牢牢掌握递归。DP很难！但真正困难的部分是找到解决方案。一旦你理解了 DP 的概念（上面应该让你明白）并且你给出了一个解决方案的草图（例如我对你问题的回答，那么它真的不难应用，因为 DP 解决方案通常非常简洁且与易于理解的递归解决方案的迭代版本相距不远。

你还应该看看memoization，有些人觉得它更容易理解，但它通常和 DP 一样有效。简而言之，记忆化采用递归函数并缓存其结果，以节省将来为相同参数重新计算结果。

score 2 · Accepted Answer

动态规划只能解决一些问题

由于尚未有人提及它，因此适用动态编程解决方案所需的属性是：

重叠的子问题。 必须可以将原始问题分解为子问题，以使某些子问题不止一次出现。与普通递归相比，DP 的优势在于这些子问题中的每一个都将只解决一次，并且在必要时保存并重用结果。换句话说，DP 算法用内存换取时间。
最佳子结构。 必须能够仅使用子问题的最优解来计算子问题的最优解。验证此属性是否成立可能需要仔细考虑。

示例：所有对最短路径

作为 DP 算法的一个典型例子，考虑使用Floyd-Warshall 算法找到图中所有顶点对之间最短路径长度的问题。

假设有n编号为 1 到的顶点n。尽管我们对计算一个函数感兴趣d(a, b)，即顶点之间的最短路径的长度a和b，但很难找到一种方法从函数的其他值有效地计算它d()。

让我们引入第三个参数c，并将其定义d(a, b, c)为之间的最短路径的长度，a并且b仅访问 1 到c之间的范围内的顶点。（它不需要访问所有这些顶点。）虽然这似乎是一个毫无意义的约束添加，但请注意我们现在有以下关系：

d(a, b, c) = min(d(a, b, c-1), d(a, c, c-1) + d(c, b, c-1))

上面的 2 个参数min()显示了 2 种可能的情况。从a到b仅使用顶点 1c到任一的最短方法：

避免（在这种情况下，它与仅使用第一个顶点c的最短路径相同），或c-1
通过c. 在这种情况下，该路径必须是从到的最短路径，然后是从a到c的最短路径c，b两条路径都被限制为仅访问介于 1 到c-1之间的顶点。我们知道，如果这种情况（通过c）更短，那么这两条路径不能访问任何相同的顶点，因为如果它们这样做了，跳过c它们之间的所有顶点（包括）会更短，所以情况 1 本来是取而代之。

这个公式满足最优子结构性质——只需要知道子问题的最优解，就可以找到更大问题的最优解。（并不是所有的问题都有这个重要的属性——例如，如果我们想找到所有顶点对之间的最长a路径，这种方法就失败了，因为从to的最长路径c可能会访问也被从 to 的最长路径访问的顶点c。b）

d(a, b, 0)知道了上面的函数关系，以及等于和之间的边长度的a边界条件b（如果不存在这样的边，则为无穷大），就可以计算的每个值d(a, b, c)，从开始c=1并一直到c=n。 d(a, b, n)是之间的最短距离，a并且b可以访问其间的任何顶点——我们正在寻找的答案。

score 1 · Accepted Answer

1

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

于 2010-11-25T14:42:06.603 回答

score 1 · Accepted Answer

几乎所有介绍算法的书籍都有一些动态规划的章节。我建议：

Cormen 等人的算法简介
算法简介： Udi Manber的创造性方法

score 1 · Accepted Answer

如果你想了解算法，我发现 MIT 有一些非常优秀的讲座视频。

例如，6.046J / 18.410J 算法介绍 (SMA 5503)看起来是一个不错的选择。

该课程涵盖动态编程以及许多其他有用的算法技术。在我个人看来，所用的书也非常出色，非常值得任何认真学习算法的人购买。

此外，该课程附带作业清单等，因此您也有可能在实践中练习该理论。

algorithm - 理解动态规划的好例子、文章、书籍

14 回答 14

自顶向下

自下而上

其他资源

示例问题

动态规划只能解决一些问题

示例：所有对最短路径

相关问题：

algorithm - 理解动态规划的好例子、文章、书籍

14 回答 14

自顶向下

自下而上

其他资源

示例问题

动态规划只能解决一些问题

示例：所有对最短路径

相关问题：

Related

Reference