动态编程是一种有用的算法，可用于通过将困难分解为较小的子问题来优化困难的问题。通过存储和重用部分解决方案，它可以避免使用贪婪算法带来的陷阱。动态编程有两种，自底向上和自顶向下。

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

自顶向下

自上而下被称为备忘录。这是存储过去的计算的想法，以避免每次都重新计算它们。

给定一个递归函数，说：

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]（最大权重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的动态编程，了解一些实践问题，这些实践问题将测试您实现和发现动态编程问题重复发生的能力。