15.1.1. 动态规划¶

动态规划是一种算法设计技术，它可以提高凡是反复求解相同子问题的固有递归算法的效率。使用动态规划需要两步：

1. 你为一个子问题被重复求解很多次的问题找出一个递归解。

2. 优化该递归算法，以消除对子问题的重复求解。 得到的算法可以是递归的，也可以是迭代的。迭代形式通常被称为动态规划。

我们首先通过一个简单的问题来看如何消除冗余：计算斐波那契数。然后我们引入背包问题，并说明如何用动态规划高效地解决它。

15.1.2. 计算斐波那契数¶

斐波那契序列通常定义如下：

下面是计算第 \(n\) 个斐波那契数的"自然"递归实现。

/** Recursively generate and return the n'th Fibonacci
    number */
static long fibr(int n) {
  // fibr(91) is the largest value that fits in a long
  if ((n <= 0) || (n > 91)) { return -1; }
  if ((n == 1) || (n == 2)) { return 1; }    // Base case
  return fibr(n-1) + fibr(n-2);      // Recursive call
}

运行它的成本是多少？嗯，计算第 \(n\) 个数的成本看起来惊人地像该数本身的大小。因为成本恰好是由完全相同的递推关系计算的！那么，它的增长率是多少呢？

让我们先来看一堆小值。然后通过比较 \(f(n-1)\) 与 \(f(n)\)，也许就能使用除法猜测（divide-and-guess）法。

顺着这个思路推下去，它似乎稳定在 1.618 的比值。假设 \(f(n)/f(n-1)\) 确实趋于一个固定值 \(x\)，让我们来验证 \(x\) 必然是多少。

对于大的 \(n\)，

我们通过相乘和重新整理得到：

随着 \(n\) 变大，这两个比值都趋于 \(x\)。所以，如果 \(x\) 存在，那么 \(x^2 - x - 1 \rightarrow 0\)。使用二次方程求根公式，唯一大于 1 的解是

因此，增长率是指数级的。 \(f(n) \approx (1.618)^n\)。

注意，即使刻度略有偏差，数值也总在正确的范围内。

为什么 fibr 这么昂贵？主要因为这个函数进行了两次递归调用，而它们所做的工作在很大程度上是冗余的。也就是说，这两次调用中的每一次都在重新计算序列的大部分内容，每个子调用也是如此，依此类推。因此，函数的较小值被重复计算了无数次。如果我们能消除这种冗余，成本将大大降低。我们采用的方法也能改进任何把大部分时间花在重复计算公共子问题上的算法。

下面的幻灯片详细展示了这个冗余问题。

Settings

Saving...
Server Error
Resubmit

观察最后的那棵树，我们看到只需要求解 7 个不同的子问题（对应斐波那契值 0 到 6）。下面的图形表示称为依赖图，它显示了这些子问题之间的依赖关系。

注意，依赖图被铺排在一张长度为 7 的一维表中，对应于算法调用的那些不同子问题。这张表可以简单地存储每个子问题的值。这样，就可以避免冗余调用，因为先前计算过的子问题的值可以从表中对应的单元格读出，无需再次重新计算。

该表格可以用于开发出两种高效的替代算法。实现这一目标的一种方法是维护一个值表，首先检查该表以确定是否可以避免计算。这种技术称为 记忆化 。以下是一个实现此功能的直接示例。请注意，它反映了原始版本的斐波那契递归算法。

static int fibrt(int n) {
  // Assume Values has at least n slots, and all
  // slots are initialized to 0
  if ((n <= 0) || (n > 91)) { return -1; }
  if (n <= 2) { return 1; }             // Base case
  if (Values[n] == 0) {
    Values[n] = fibrt(n-1) + fibrt(n-2);
  }
  return Values[n];
}

这个版本的算法不会把任何值计算超过一次，所以其成本是线性的。相应的递归树如下所示。注意，每个递归调用的首次出现会引发两次递归调用。但是，这种调用的后续出现不会产生额外的调用，因为它们只是读取对应单元格的内容。

第二种方法称为 制表法 。必须分析依赖图，以推断子问题替代计算顺序。唯一限制是子问题只能在其依赖子问题已经计算的情况下进行计算。此外，每个子问题的值必须存储在表中。在计算斐波那契数列的值时，我们逆转顺序从起点计算序列，并通过简单的循环实现这一点。不幸的是，由于它与原始递归算法没有任何相似性，因此无法机械地从原始递归形式转换为动态规划形式。

还可以做进一步的优化。当然，我们其实并不需要存储全部值的表，因为后续计算并不需要访问所有的先前子问题（这一点可以从依赖图中看出）。相反，我们可以从 0 和 1 开始由底层向上构建函数值，直到 \(n\)，而不是从 \(n\) 反向往下到 0 和 1。从底部向上时，我们只需存储函数的前两个值，正如我们的迭代版本所做的那样。

/** Iteratively generate and return the n'th Fibonacci
    number */
static long fibi(int n) {
  // fibr(91) is the largest value that fits in a long
  if ((n <= 0) || (n > 91)) { return -1; }
  long curr, prev, past;
  if ((n == 1) || (n == 2)) { return 1; }
  curr = prev = 1;     // curr holds current Fib value
  for (int i=3; i<=n; i++) { // Compute next value
    past = prev;             // past holds fibi(i-2)
    prev = curr;             // prev holds fibi(i-1)
    curr = past + prev;      // curr now holds fibi(i)
  }
  return curr;
}

子问题的重复计算在许多算法中出现。像对 fibi 那样只存储少量先前结果的情况并不常见。因此，在很多情况下，完整存储一张子结果表将会很有用。

上文展示的、通过存储子问题结果表来设计算法的方法，在应用于优化算法时被称为 动态规划。这个名称有些晦涩，因为它与把子问题存入一张表的实际过程并没有太多明显的相似之处。不过，它最初来自动态控制系统的领域，该领域在我们所理解的计算机编程出现之前就已起步。在那个领域，把预先计算好的值存入表中供以后复用被称为"programming"。动态规划算法通常用上文描述的制表技术来实现。因此，与 fibrt 相比， fibi 更好地代表了动态规划最常见的形式，尽管它并没有使用完整的表。

15.1.3. 背包问题¶

接下来我们考虑一个问题，它在各种各样的商业场景中以许多变体出现。许多企业需要以最高的效率打包物品。描述这一基本思想的一种方式是：把物品装进背包，因此我们称之为 背包问题。我们首先定义背包问题的一种特定形式，然后讨论一种基于动态规划求解它的算法。这个问题还有许多其他版本。有些版本要求在容量内装入尽可能多的物品，另一些版本在大小之外还给物品引入价值。我们将研究一个相对容易理解的变体。

假设我们有一个具有一定空间的背包，我们用整数值 \(K\) 来定义它。我们还有 \(n\) 件物品，每件都有一定的大小，第 \(i\) 件物品具有整数大小 \(k_i\)。问题是从这 \(n\) 件物品中找出一个子集，使其大小之和恰好等于 \(K\)，如果存在的话。例如，如果我们的背包容量 \(K = 5\)，两件物品的大小为 \(k_1 = 2\) 和 \(k_2 = 4\)，那么不存在这样的子集。但如果我们再加上第三件大小为 \(k_3 = 1\) 的物品，那么我们就可以用第二件和第三件物品恰好装满背包。我们可以把问题更正式地定义为：找出满足下列条件的 \(S \subset \{1, 2, ..., n\}\)：

如果你试着求解这些例子，你可能会发现自己做了大量的试错和大量的回溯。为了想出一个算法，我们需要一种组织化的方式遍历所有可能的子集。有没有办法把问题缩小，以便我们应用递归？输入本质上由两部分组成：背包大小 \(K\) 和这 \(n\) 件物品。试图把背包拆成几块再求解各子块很可能对我们没有多大帮助（因为我们已然看到，知道大小为 163 的背包的答案对求解大小为 164 的背包问题毫无帮助）。

那么，对于用或不使用第 \(n\) 件物品来求解问题，我们能说些什么呢？这似乎指出了分解问题的一条途径。如果解不需要第 \(n\) 件物品（也就是说，如果我们用前 \(n-1\) 件物品就能求解问题），那么在第 \(n\) 件物品可用时我们也能求解问题（我们只需忽略它）。另一方面，如果我们确实把第 \(n\) 件物品纳入解子集，那么现在就需要用前 \(n-1\) 件物品以及一个大小为 \(K - k_n\) 的背包来求解问题（因为第 \(n\) 件物品在背包中占用了 \(k_n\) 的空间）。

为组织这一过程，我们可以用两个参数来定义问题：背包大小 \(K\) 和物品数量 \(n\)。把问题的一个给定实例记为 \(P(n, K)\)。现在我们可以说，\(P(n, K)\) 有解当且仅当 \(P(n-1, K)\) 或 \(P(n-1, K-k_n)\) 有解。也就是说，只有当我们能求解使用或不使用第 \(n\) 件物品的某个子问题时，才能求解 \(P(n, K)\)。当然，物品的排列顺序是任意的。我们只是需要给它们某种顺序，以便理清头绪。

顺着这个思路，要求解任何规模为 \(n-1\) 的子问题，我们只需要求解两个规模为 \(n-2\) 的子问题。依此类推，直到我们只剩下 1 件物品，它要么装满背包，要么装不满。

继续这个思路，对于大小为 \(n-1\) 的子问题，我们需要解决两个大小为 \(n-2\) 的子问题。以此类推，直到我们只剩下一个物品，要么适合背包，要么不适合。假设 \(P(i, S)\) 表示从第 i 个对象起的问题，且背包中还有大小为 s 的空间，则以下算法表达了这些思想。

虽然这个算法是正确的，但它很自然地导致由递推关系 \(\mathbf{T}(n) = 2\mathbf{T}(n-1) + c = \Theta(2^n)\) 所表示的成本。这可能非常昂贵！

但是……我们应该很快意识到，只有 \(n(K+1)\) 个子问题需要求解！显然，很可能有许多子问题被反复求解。这是应用动态规划的天赐良机。如果我们画出这个朴素递归算法的递归树，并导出相应的依赖图，就会注意到，所有递归调用都可以铺排在一个大小为 \(n \times K+1\) 的数组上，用来存放所有子问题 \(P(i, k), 0 \leq i \leq n-1, 0 \leq k \leq K\) 的解。

如上所述，实际求解这个问题有两种途径。一种是记忆化，即从规模为 \(P(n, K)\) 的问题入手，递归调用求解子问题，每次查数组看某个子问题是否已求解，并在每次得到新的子问题解时在数组中填入对应的单元格。另一种是制表。可以想见，我们可以采用好几种计算顺序，不过最"自然"的是从第 0 行开始填数组（第 0 行只有对大小为 \(k_0\) 的背包才表示成功解）。然后我们从 \(i=1\) 到 \(n\) 填充后面的行。

换句话说，数组中的一个新槽位至多只需查看前一行的两个槽位即可得到解。由于填充数组中的每个槽位只需常数时间，算法的总成本为 \(\Theta(nK)\)。

15.1.4. 链式矩阵乘法¶

许多工程问题需要把大量矩阵相乘。有时是相当大的矩阵。事实证明，我们以什么顺序进行计算会产生很大的差别。

首先，让我们回顾一下基本知识。如果我们有两个矩阵（一个 \(r\) 行 \(s\) 列，另一个 \(s\) 行 \(t\) 列），那么结果将是一个 \(r\) 行 \(t\) 列的矩阵。（别忘了，只有当第一个矩阵的列数等于第二个矩阵的行数时，我们才能把两个矩阵相乘。）我们真正关心的是，矩阵乘法的成本由必须相乘在一起的项数所支配。这里将总共需要 \(r \times s \times t\) 次乘法（外加一些加法，由于时间以乘法为主，我们可以忽略不计）。

另一件要意识到的事情是：当然，先乘 \(A \times B\) 还是 \(B \times A\) 是有区别的。但我们假设已经确定了它们相乘的顺序（应当是 \(A \times B\)）。对于所有乘法，我们假设行和列适当地对齐，使这些乘法可行。鉴于这一切，如果有许多矩阵相乘，我们仍然有选择要做。我们需要考虑的是：如果想乘三个矩阵，并且知道了顺序，我们仍然有如何分组的选择。假设它们分别命名为 \(A\)、\(B\) 和 \(C\)，乘法顺序将是 \(A \times B \times C\)。但我们可以通过先算 \(A \times (B \times C)\) 或先算 \((A \times B) \times C\) 来实现，最终答案是一样的。然而，如下文所见，在获得该答案的成本方面，以哪种方式做可能差别很大。

Settings

Saving...
Server Error
Resubmit

要高效地解决这个问题（即如何分组乘法的顺序），我们应该注意到递归树中有大量重复的结点。但实际需要求解的子问题相对有限。例如，我们反复需要决定乘 ABC 的最佳顺序。而要求解它，我们又反复计算 AB 的成本和 BC 的成本。加速的一种方式自然是每当计算出答案就记住它们（使用记忆化）。每当我们再次问起这个问题时，直接使用存储的结果。这意味着我们要有好的方式记住把它们存在哪里，也就是说，如何组织子问题，以便轻松检查这个问题是否已经求解。

那么，当有 \(n\) 个矩阵要相乘（标注为 1 到 \(n\)）时，我们如何组织子问题呢？下面的依赖图可以帮助我们看清这个算法。为了更好地看清这些关系，我们将只看相乘 ABCD 的依赖图，而不是 ABCDE。

由此我们看到，我们可以使用一张大小为 \(n \times n\) 的表。在这张表中，位于 \([i, j]\) 的条目是把矩阵 \(i\) 乘到 \(j\) 的最佳解的成本。所以，左上角（条目 \([1, n]\)）就是完整解。主对角线上的条目只是一个矩阵（没有乘法）。只有左上三角区域有条目（因为把矩阵 5 乘到矩阵 3 的成本毫无意义，只有把矩阵 3 乘到矩阵 5 才有意义）。

现在，当我们需要计算从 \(i\) 到 \(j\) 的一系列矩阵时，只需查看表中位置 \([i, j]\)。如果那里有答案，就用它。否则，就进行计算，并把结果记在表中。