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

Question

关闭。这个问题是off-topic .它目前不接受答案。




9年前关闭。










锁定。这个问题及其答案是locked因为这个问题是题外话，但具有历史意义。它目前不接受新的答案或互动。








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

Getting the lowest possible sum from numbers' difference

所以，你能建议我好书或文章 (最好有真实代码的例子)这会解释什么是动态编程？我真的想要首先简单的例子，然后我会继续。

Answer 1

Dynamic programming是一种有用的算法，可用于通过将难题分解为更小的子问题来优化难题。通过存储和重用部分解决方案，它设法避免了使用贪婪算法的陷阱。动态规划有自底向上和自顶向下两种。
为了使用动态规划可解决问题，该问题必须具有所谓的 optimal substructure 的性质。 .这意味着，如果将问题分解为一系列子问题并找到每个子问题的最佳解决方案，那么最终解决方案将通过这些子问题的解决方案实现。没有这种结构的问题不能用动态规划解决。
自顶向下
自上而下更广为人知的是 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 件商品的商店。问题是你的 tiny knapsack最多只能容纳 W kg。知道每件物品的重量 (w[i]) 和值(value) (v[i])，你想最大化你的赃物的值(value)，这些物品的总重量最多为 W。对于每件物品，你必须做出二元选择 -要么接受，要么离开它。
现在，您需要找出子问题是什么。作为一个非常聪明的小偷，您意识到具有最大权重 w 的给定项目 i 的最大值可以表示为 m[i, w]。此外，m[0, w](0 项最多权重 w)和 m[i, 0](i 项最大权重为 0)将始终等于 0 值。
所以，

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

戴上思考型全 mask 后，您会注意到，如果您的袋子装满了尽可能多的重量，则不能考虑新物品，除非其重量小于或等于您的最大重量与最大重量之间的差值。袋子的当前重量。您可能想要考虑某件物品的另一种情况是，它的重量小于或等于袋子中某件物品的重量，但值(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

这些是上述的递推关系。一旦有了这些关系，编写算法就非常容易(而且很短!)。

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]

其他资源

Introduction to Algorithms

Programming Challenges

Algorithm Design Manual

示例问题
幸运的是，在竞争性编程方面，动态编程已经成为现实。退房 Dynamic Programming on UVAJudge对于一些练习题，这些练习题将测试您实现动态规划问题并找到重复的能力。