算法——动态规划：基础

一、基本介绍

动态规划（Dynamic Programming，DP）是求解 多阶段决策 问题 最优化 的一种算法思想，它将 大问题分解成更简单的子问题，对 整体问题的最优解 取决于 子问题的最优解。用于解决具有 重叠子问题、最优子结构 特征的问题。关于 重叠子问题 和 最优子结构，在案例中会进行介绍。

二、案例——斐波那契数列

1. 基本介绍

斐波那契数列 是一个 递推数列，它的每个数字是前面两个数字之和，如 $1,1,2,3,5,8\cdots$。其递推公式为 $f(n)=f(n-1)+f(n-2)$，$n\ge 3$ 且 $n\in N_{+}$，此外 $f(1)=1,f(2)=1$。总结就是如下的公式：
$$f(n)=\{\begin{array}{l}1,n=1,2\\ f(n-1)+f(n-2),n\ge 3\end{array},n\in N_{+}$$

2. 递归实现

递归的实现很简单，只看递推公式就可以了。代码如下：

int f(int n) {if (n == 1 || n == 2) {return 1;}return f(n - 1) + f(n - 2);
}

可以发现，每计算一个总问题 $f(n)$，就需要计算两个子问题 $f(n-1),f(n-2)$，从而导致该实现的时间复杂度为 $O(2^n)$，算是非常差劲的时间复杂度了，这时就需要考虑使用 动态规划 进行优化。

3. 动态规划

前面提到过，使用 动态规划 解决的问题有两个特征。

3.1 重叠子问题

重叠子问题 有两个特点：

• 子问题是原大问题的小版本，计算步骤完全一样。
• 计算大问题时，需要多次 重复 计算小问题。

在斐波那契数列中，计算 $f(5)$ 会被分解成以下的子问题：

可以发现，$f(3)$ 被计算了多次，实际上只需要计算一次，保存其结果即可。

一个子问题的多次重复计算会耗费大量时间，这里就能想到一种策略——以空间换时间：保存已经计算过的子问题的结果。在之后的使用时，直接用保存的结果进行计算。这就是 动态规划 的思想，避免重复计算某个子问题，但会耗费更多的空间。

使用这种策略，就可以将计算 $f(5)$ 优化成以下的子问题：

3.2 最优子结构

最优子结构 也有两个特点：

• 大问题的最优解 包含 小问题的最优解。
• 可以通过小问题的最优解 推导出 大问题的最优解。

在斐波那契数列中，要计算 $f(n)$，就得先计算 $f(n-1),f(n-2)$。其中，$f(n)$ 是大问题的最优解，$f(n-1),f(n-2)$ 是小问题的最优解。由于斐波那契数列比较简单，每个 $n$ 只对应一个解，所以没有体现出 最优 的概念，之后的各种背包问题会有 最优 的概念。

3.3 无后效性

动态规划 中还有一个名词：无后效性，它也比较重要。

无后效性 是使用 动态规划 的 必要条件，如果问题不满足 无后效性，则无法使用动态规划。无后效性 意味着 只关心结果，不关心过程，即只需要保存计算的结果，不需要保存计算的过程。

在斐波那契数列中，要计算 $f(n)$，就得先知道 $f(n-1),f(n-2)$ 的结果，而不需要知道它们是如何计算的。

3.4 性质的总结

最优子结构 所具有的性质（可以通过小问题的最优解 推导出 大问题的最优解）足以说明该问题有 无后效性。只要一个问题具有 重叠子问题 和 最优子结构 的特征，就可以使用 动态规划 的思想进行优化。

4. 使用 动态规划 的思想实现

动态规划 有两种编程思路：

• 自顶向下（Top-Down）：先大问题，再小问题。通常采用 递归 实现，也叫 记忆化搜索。
• 自底向上（Bottom-Up）：先小问题，再大问题。通常采用 递推 实现。

说明：此处的“先”不代表“先解决”，而是代表“先遍历到”，无论哪种实现方式，都是先解决小问题，然后才能解决大问题，并且所有问题都只被解决一次。此外，这两种思路的时间复杂度和空间复杂度是一样的。

4.1 自顶向下 的 递归

• 中心思想：先 考虑 大问题，再缩小到小问题，直到最小的问题，最后从小到大依次解决所有问题。
• 实现：解决完子问题后就将其结果保存起来，如果需要再次使用，直接获取保存的结果。

使用 递归 的 动态规划 的思想，实现的 斐波那契数列 如下所示：

const int N = 255; // N 是一个常数，表示数组的长度
int memoize[N]; // 用于保存结果的数组
int f(int n) {if (n == 1 || n == 2) {return 1;}if (memoize[n] != 0) { // 如果数组中保存了 f(n)return memoize[n]; // 则直接将其返回}// 否则计算出 f(n)，先保存它，然后再返回memoize[n] = f(n - 1) + f(n - 2);return memoize[n];
}

这种方式的时间复杂度为 $O(n)$。

4.2 自底向上 的 递推

• 中心思想：先 解决 子问题，再递推到大问题。
• 实现：使用若干个 for 循环填写一维或多维数组 dp，dp 的每个元素都有具体含义。
• 注意：递推 避免了多层递归导致的 栈溢出 问题，使用动态规划时一般采用这种思路。

使用 递推 的 动态规划 的思想，实现的 斐波那契数列 如下所示：

const int N = 255; // N 是一个常数，表示数组的长度
int dp[N]; // dp[i] 表示 f(i)
int f(int n) {dp[1] = dp[2] = 1; // 初始状态for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}

这种方式的时间复杂度也为 $O(n)$。

4.3 两种思路的简单比较

• 自顶向下 的 递归：能够更宏观地把握问题、认清问题的本质。
• 自底向上 的 递推：编码更直接，不会造成 栈溢出 问题。

三、总结

动态规划 经常用于具有 重叠子问题 和 最优子结构 特征的问题，使用 空间 换 时间 的思想，有 递归 和 递推 两种实现方式，一般使用 递推 的方式，所以经常在动态规划的题解中看到 dp 数组。

本文介绍了动态规划中最基础的知识，更高级的知识（如滚动数组、背包问题等）将会在之后的文章中依次展开。