当前位置：文江博客话题详情

algorithm language-agnostic dynamic-programming

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

发布于 2024-10-04 13:46:35 字数 276 浏览 6 评论 0 原文

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

获取尽可能低的值数字差求和

那么，你能给我推荐好书或文章（最好有带有真实代码的示例），它们可以解释什么是动态规划吗？我真的想要首先简单的例子，然后我会继续。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

对你再特殊 2024-10-11 13:46:35

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

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

自上而下

自上而下更广为人知的名称是记忆化。这是存储过去的计算以避免每次重新计算的想法。

给定一个递归函数，比如说：

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 is a useful type of algorithm that can be used to optimize hard problems by breaking them up into smaller subproblems. By storing and re-using partial solutions, it manages to avoid the pitfalls of using a greedy algorithm. There are two kinds of dynamic programming, bottom-up and top-down.

In order for a problem to be solvable using dynamic programming, the problem must possess the property of what is called an optimal substructure. This means that, if the problem was broken up into a series of subproblems and the optimal solution for each subproblem was found, then the resulting solution would be realized through the solution to these subproblems. A problem that does not have this structure cannot be solved with dynamic programming.

Top-Down

Top-down is better known as memoization. It is the idea of storing past calculations in order to avoid re-calculating them each time.

Given a recursive function, say:

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

We can easily write this recursively from its mathematic form as:

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

Now, anyone that has been programming for awhile or knows a thing or two about algorithmic efficiency will tell you that this is a terrible idea. The reason is that, at each step, you must to re-calculate the value of fib(i), where i is 2..n-2.

A more efficient example of this is storing these values, creating a top-down dynamic programming algorithm.

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)

By doing this, we calculate fib(i) at most once.

Bottom-Up

Bottom-up uses the same technique of memoization that is used in top-down. The difference, however, is that bottom-up uses comparative sub-problems known as recurrences to optimize your final result.

In most bottom-up dynamic programming problems, you are often trying to either minimize or maximize a decision. You are given two (or more) options at any given point and you have to decide which is more optimal for the problem you're trying to solve. These decisions, however, are based on previous choices you made.

By making the most optimal decision at each point (each subproblem), you are making sure that your overall result is the most optimal.

The most difficult part of these problems is finding the recurrence relationships for solving your problem.

To pay for a bunch of algorithm textbooks, you plan to rob a store that has n items. The problem is that your tiny knapsack can only hold at most W kg. Knowing the weight (w[i]) and value (v[i]) of each item, you want to maximize the value of your stolen goods that all together weight at most W. For each item, you must make a binary choice - take it or leave it.

Now, you need to find what the subproblem is. Being a very bright thief, you realize that the maximum value of a given item, i, with a maximum weight, w, can be represented m[i, w]. In addition, m[0, w] (0 items at most weight w) and m[i, 0] (i items with 0 max weight) will always be equal to 0 value.

so,

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

With your thinking full-face mask on, you notice that if you have filled your bag with as much weight as you can, a new item can't be considered unless its weight is less than or equal to the difference between your max weight and the current weight of the bag. Another case where you might want to consider an item is if it has less than or equal weight of an item in the bag but more value.

 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

These are the recurrence relations described above. Once you have these relations, writing the algorithm is very easy (and short!).

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]

Additional Resources

Example Problems

Luckily, dynamic programming has become really in when it comes to competitive programming. Check out Dynamic Programming on UVAJudge for some practice problems that will test your ability to implement and find recurrences for dynamic programming problems.

回复收藏 0 原文

千纸鹤带着心事 2024-10-11 13:46:35

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

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

回复收藏 0 原文

仙气飘飘 2024-10-11 13:46:35

从

关于动态编程的维基百科文章开始，然后
我建议您阅读topcoder 中的这篇文章
ch6 关于算法中的动态规划 (Vazirani)
算法设计手册中的动态规划章节
算法经典书籍中的动态规划章节 (算法简介）

如果你想测试一下自己，我对在线法官的选择是

当然

还有算法师动态规划类

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

毕竟，如果你无法解决问题，所以这里存在很多算法迷

回复收藏 0 原文

南城旧梦 2024-10-11 13:46:35

请参阅下文

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

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

学习动态规划后，您可以通过解决 UVA问题，UVA 讨论区

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

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

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

另外，您还应该看看动态编程中的Memoization。

回复收藏 0 原文

云醉月微眠 2024-10-11 13:46:35

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

传统上，DP 是通过例子来教授的：算法是用术语来表示的
存储中间问题解决方案的表条目之间的重复，
从该表中，通过一些案例分析构建了整体解决方案。

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

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

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

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

回复收藏 0 原文

左耳近心 2024-10-11 13:46:35

这篇 USACO 文章是了解 DP 基础知识的一个很好的起点以及它如何能够带来巨大的加速。然后查看这篇 TopCoder 文章，其中还介绍了基础知识，但写得不太好。 CMU的这个教程也很不错。一旦您理解了这一点，您将需要跳跃到 2D DP 来解决您提到的问题。通读这篇 Topcoder 文章，直至并包括苹果问题（标记为中级）。

您可能还会发现观看这个麻省理工学院视频讲座很有用，具体取决于您选择事物的程度从视频中。

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

看看 memoization，有些人发现它更容易理解，但它通常与 DP 一样有效。简单地解释一下，记忆化采用递归函数并缓存其结果，以便将来重新计算相同参数的结果。

回复收藏 0 原文

反差帅 2024-10-11 13:46:35

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

由于还没有人提到过，动态规划解决方案适用所需的属性是：

重叠子问题。 必须能够打破原始问题以某些子问题多次出现的方式分解子问题。与普通递归相比，DP 的优点是每个子问题都只会被解决一次，并且结果会被保存并在必要时重用。换句话说，DP 算法用内存换取时间。
最优子结构。必须能够仅使用子问题的最优解决方案来计算子问题的最优解决方案。验证此属性是否成立可能需要仔细思考。

示例：所有对最短路径

作为 DP 算法的典型示例，请考虑使用 Floyd-Warshall 算法。

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

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

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

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

避免 c （在在这种情况下，它与仅使用第一个 c-1 顶点的最短路径相同），或
通过 c 进行。在这种情况下，该路径必须是从 a 到 c 的最短路径，后跟从 c 到 b 的最短路径code>，两条路径都限制为仅访问 1 到 c-1 范围内的顶点。我们知道，如果这种情况（通过c）更短，那么这两条路径就不能访问任何相同的顶点，因为如果它们这样做了，跳过所有顶点（包括 >c) 位于它们之间，因此会选择情况 1。

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

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

Only some problems can be solved with Dynamic Programming

Since no-one has mentioned it yet, the properties needed for a dynamic programming solution to be applicable are:

Overlapping subproblems. It must be possible to break the original problem down into subproblems in such a way that some subproblems occur more than once. The advantage of DP over plain recursion is that each of these subproblems will be solved only once, and the results saved and reused if necessary. In other words, DP algorithms trade memory for time.
Optimal substructure. It must be possible to calculate the optimal solution to a subproblem using only the optimal solutions to subproblems. Verifying that this property holds can require some careful thinking.

Example: All-Pairs Shortest Paths

As a typical example of a DP algorithm, consider the problem of finding the lengths of the shortest paths between all pairs of vertices in a graph using the Floyd-Warshall algorithm.

Suppose there are n vertices numbered 1 to n. Although we are interested in calculating a function d(a, b), the length of the shortest path between vertices a and b, it's difficult to find a way to calculate this efficiently from other values of the function d().

Let's introduce a third parameter c, and define d(a, b, c) to be the length of the shortest path between a and b that visits only vertices in the range 1 to c in between. (It need not visit all those vertices.) Although this seems like a pointless constraint to add, notice that we now have the following relationship:

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

The 2 arguments to min() above show the 2 possible cases. The shortest way to get from a to b using only the vertices 1 to c either:

Avoids c (in which case it's the same as the shortest path using only the first c-1 vertices), or
Goes via c. In this case, this path must be the shortest path from a to c followed by the shortest path from c to b, with both paths constrained to visit only vertices in the range 1 to c-1 in between. We know that if this case (going via c) is shorter, then these 2 paths cannot visit any of the same vertices, because if they did it would be shorter still to skip all vertices (including c) between them, so case 1 would have been picked instead.

This formulation satisfies the optimal substructure property -- it is only necessary to know the optimal solutions to subproblems to find the optimal solution to a larger problem. (Not all problems have this important property -- e.g. if we wanted to find the longest paths between all pairs of vertices, this approach breaks down because the longest path from a to c may visit vertices that are also visited by the longest path from c to b.)

Knowing the above functional relationship, and the boundary condition that d(a, b, 0) is equal to the length of the edge between a and b (or infinity if no such edge exists), it's possible to calculate every value of d(a, b, c), starting from c=1 and working up to c=n. d(a, b, n) is the shortest distance between a and b that can visit any vertex in between -- the answer we are looking for.