一、什么是动态规划？
动态规划（Dynamic Programming, DP）被看作是递归的一种优化，针对的是要计算很多重叠的子问题（Overlapping Subproblems）的情况。它的思想是将一个大问题分解为若干个子问题，这些子问题可能会被重复调用多次，它把子问题的结果存储下来，当子问题被调用多次的时候，直接读取存储好的结果，不再重复计算。
例如，在解决“斐波那契数”问题时，我们使用递归方法的一种实现如下：
// C++, Recursion solution for Fibonacci number
int fib(int n)
{
if (n <= 1) {
return n;
} else {
return fib(n-1) + fib(n-2);
}
}
在计算 fib(5) 的时候，我们可以画出下面的树状分解图 [1]：
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
从树状分解图可以看出，在计算 fib(5) 的时候，fib(1) 被计算了 5 次，fib(2) 被计算了 3 次，fib(3) 被计算了 2 次，fib(4) 被计算了 1 次，这就说明其中有很多子问题的计算都是重叠的。
针对斐波那契数问题，下面是采用动态规划方法的一种实现：
// C++, Dynamic Programming, Tabulation (Bottom Up)
int fib(int n)
{
int f[n+1];
int i;
f[0] = 0; f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}
总结一下：动态规划会把子问题的结果存储下来，再次遇到重叠的子问题时，就直接返回存储好的结果，从而避免重复计算。
二、动态规划适合解决什么样的问题？
一般具有以下两种属性的问题可以用动态规划来解决：
- 重叠子问题（Overlapping Subproblems）
- 最优子结构（Optimal Substructure）
重叠子问题（Overlapping Subproblems）
适合用动态规划解决的问题的特点之一是具有“重复的子问题”。动态规划和分治法（Divide and Conquer）都能将一个大问题分解为若干个小问题，有什么区别呢？关键在于是这些”小问题“会不会被被重复调用 [2]。
例如“二分搜索（Binary Search）”问题，没有重复调用的子问题，所以就不适合用动态规划去解决。而本文开始时介绍了斐波那契数问题，在计算 fib(n) 的时候，需要反复利用 fib(1), fib(2)... 的值，这就是典型的具有“重复的子问题”的特点。前面已经针对这一点说了足够多的篇幅，这里不再赘述。
最优子结构（Optimal Substructure）
引入一个“走台阶”问题：有 10 个阶梯，一个人每一步只能跨一个台阶或是两个台阶，问这个人一共有多少种走法 [2, 5]？
我们可以将这个问题进行抽象，把每个台阶都认为是“图论”里的一个点，然后有桥梁把这些点连接起来，之后问题就转换成了从 node 0 到 node 10 一共有多少种不同的路可以走 [2]：
走台阶问题抽象成路径问题的示意图（图片参考自 [2] 中知乎用户牛岱的回答）
我们记 node 0 到 node n 总共有 F(n) 条不同的路可以走。走到 node 10 的最后一步有两种情况，一种是从 node 9 走过去，一种是从 node 8 直接走过去。注意，node 9 --> node 10 已经包含了 node 8 --> node 9 --> node 10 这种情况。假设我们已经知道了 F(9)、F(8)，经过分析，我们可以得到 F(10) = F(9) + F(8)。更一般的，我们可以推出 F(n) = F(n-1) + F(n-2)，这里 n >= 3。
在这个问题中，node 8 和 node 9 是从 node 0 通向 node 10 路径的一部分，而node 0 --> ... --> node 10 这个问题可以分解为node 0 --> ... --> node 8 (--> node 10) 和 node 0 --> ... --> node 9 (--> 10) 两个子问题。因此，我们就称 node 8 和 node 9 是 node 10 的最优子结构。
另外一个例子是最短路径问题（The Shortest Path Problem），也具有最优子结构的特点：如果 node x 是 node u --> ... --> node v 的最短路径中的一个结点，那么这个最短路径一定可以分解成 node u --> ... --> node x 和 node x --> ... --> node v 两个子问题。与之相对的，最长路径问题（The Longest Path Problem）就不具备这个特点。
三、怎样解决动态规划问题？
前面已经了解了什么是动态规划，以及动态规划的两大特点。那究竟该怎么解决动态规划问题呢 [4]？
1. 首先判断一个问题是否为动态规划问题
前面讲了动态规划的重叠子问题、最优子结构两个特性，可以根据是否具有这两个特性进行判断。一般来说，所有动态规划问题都满足重叠子问题特性，大多数经典动态规划问题也满足最优子结构特性 [4]。
注意：按照 [5] 的介绍，似乎所有的动态规划问题也都满足最优子结构特性。我觉得这个不是特别重要，具体问题具体分析，看怎么理解吧。
通常情况下，那些求解最大、最小数量、计算某种条件或者概率下的排列数目等问题都可以用动态规划来求解。最重要的还是观察这些问题是否具有重叠的子问题。
2. 用最少的参数来表示状态
动态规划问题的核心就是状态（State）和状态之间的转移（State Transition） [4]。
什么是动态规划问题的“状态”？前面我们知道，动态规划问题可以分解为一个一个的子问题，子问题和最终的求解目标之间有一个先后的递进关系。按我自己的理解，状态就是在动态规划问题中所处的位置。我这里把决定状态的参数称为状态参数，状态参数能唯一确定一个状态，代表着我们当前子问题能达到的目标。
例如，在斐波那契数问题中，我们用状态参数 n 来表示我们我们计算到了第 n 个斐波那契数；在走台阶问题中，我们用状态参数 n 来表示我们走到了第 n 个台阶；在 0-1 背包问题（0-1 Knapsack Problem）中，我们用状态参数 index 和 weight 来决定我们所能取得的收益。
为了使状态空间足够小，在确定动态规划问题中的状态时，表示状态的参数应该越少越好。我们应该谨慎地选取状态参数，因为这将决定我们的状态转移方程该如何构造。
3. 确定状态转移方程
确定状态转移方程是动态规划问题中最难的一个环节。
按照我的理解，状态转移方程跟递归问题中的递推关系是等价的。状态转移方程表示了一个状态和它前面的一个或多个状态之间的关系。
在确定状态转移方程时，我们可以先假设一个一般状态，然后推出我们能如何从前面的状态转移到这个状态。例如，在斐波那契数问题中，我们用 F(n) 表示第 n 个状态，也就是第 n 个斐波那契数。然后我们思考怎么能得到 F(n)。经过分析，F(n) 是第 n-1 个斐波那契数和第 n-2 个斐波那契数的和，所以 F(n) = F(n-1) + F(n-2)，这就是我们得到的状态转移方程。
4. 确定问题的边界
问题的边界就是递归方程的退出条件，一般和问题中的初始情况、最简单的情况或限制条件相对应。如果一个问题没有边界，将永远无法得到有限的结果 [5]。
例如，在斐波那契数问题中，F(1) 和 F(2) 是问题的初始情况，无需计算就可以得到结果，也不需要继续简化，它们就是这个问题的边界。在 0-1 背包问题中，除了考虑初始情况什么物品都不取，还要考虑是否超出了重量限制 W，它们都是问题的边界。
5. 用记忆表法或表格法求解问题
确定了递归方程，又确定了问题的边界，我们就可以实现递归了。在递归的基础上，我们利用动态规划进行求解，将其重叠的子问题的结果存储下来，避免重复的计算。那么，该如何存储重叠子问题的结果呢？
动态规划有两种做法来存储重叠子问题的结果：自上而下（Top Down）的记忆表法（Memoization）和自底向上（Bottom Up）的表格法（Tabulation）。
什么叫自上而下和自底向上呢？可以通过下面两个版本的说法进行区分 [1]：
- 自上而下：为了掌握动态规划，我需要各种动态规划问题的练习，但是练习之前我得先了解动态规划的理论知识。
- 自底向上：我先了解动态规划的理论，然后我进行各种动态规划问题的练习，最终我要掌握动态规划。
上面两个说法意思是一样的，但是却代表了两种不同的思想。在动态规划中，这两种思想也对应着不同的实现方式。下面还是以斐波那契数问题为例，分别进行介绍。
记忆表法——自上而下
记忆表法和递归法都是自上而下的思想。先回顾一下文章开头的斐波那契数问题递归实现：
时间复杂度：
空间复杂度：（递归问题的空间复杂度和生成的递归树的最大深度成正比 [6]，递归树最大深度为
，每次调用递归空间复杂度为 O(1)，所以 n* O(1) = O(n)）
// C++, Recursion solution for Fibonacci number
int fib(int n)
{
if (n <= 1) {
return n;
} else {
return fib(n-1) + fib(n-2);
}
}
为了避免重复计算 fib(k)，我们可以将其结果存储到一个全局的查找表（Lookup Table）中，这也是为什么称这种方法为“记忆表法”。在计算 fib(k) 时，如果查找表中还没有存储结果，就进行计算，并将结果存储到查找表中；如果查找表中已经有结果了，就不进行计算，直接返回存储的结果。实现如下：
时间复杂度：
空间复杂度：
// C++, Dynamic Programming, Memoization (Top Down)
#define MAX 100
#define NIL -1
int lookup[MAX];
void _initialize()
{
memset(lookup, NIL, MAX); // initialize lookup table with NIL
}
int fib(int n)
{
if (lookup[n] == NIL) {
if (n <= 1)
lookup[n] = n;
else
lookup[n] = fib(n-1) + fib(n-2);
}
return lookup[n];
}
表格法——自底向上
表格法的思想是自底向上的，意思是考虑从初始状态转换到目标状态的过程。假设我们的目标状态是 F(n)，我们从 F(0) 和 F(1) 状态出发，利用状态转移方程，我们可以得到状态 F(2) = F(1) + F(0)，F(3) = F(2) + F(1)……最终得到状态 F(n)。实现如下：
时间复杂度：
空间复杂度：
// C++, Dynamic Programming, Tabulation (Bottom Up)
int fib(int n)
{
int f[n+1];
int i;
f[0] = 0; f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}
为什么称这种方法为“表格法”呢？我们可以考虑上面代码在运行时 f[n+1] 这个数组的填充情况：
i | fib i | fib i | fib i | fib
----+----- ----+----- ----+----- ----+-----
0 | 0 ---> 0 | 0 ---> 0 | 0 ---> 0 | 0 ---> ...
1 | 1 1 | 1 1 | 1 1 | 1
2 | 1 2 | 1 2 | 1
3 | 2 3 | 2
4 | 3
可以看出，求解 fib(n) 的过程，就是将上面表格的一项项内容顺序填充的过程，所以称为“表格法”。
由于在表格填写的过程中，我们每次填写都只用到了前面的两项，所以我们没有必要将整张表格都存储下来：
时间复杂度：
空间复杂度：
// C++, Dynamic Programming, Tabulation (Bottom Up), Optimized
int fib(int n)
{
int i, a = 0, b = 1, c;
for (i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
（注意：[5] 中认为，只有上面这个经过优化的表格法才叫动态规划算法。）
记忆表法 vs. 表格法
参考 [1]，整理了下面的表格：
| 记忆表法 | 表格法 | |
|---|---|---|
| 状态 | 状态之间的关系实现起来比较容易 | 状态之间的关系实现起来比较困难 |
| 代码 | 代码比较容易、不复杂 | 当条件很多时，代码比较复杂 |
| 速度 | 慢，因为需要递归调用并返回 | 快，直接从表格中读取前面的状态值 |
| 子问题 | 只解决那些确实需要解决的子问题 | 所有的子问题都需要解决一次 |
| 表格记录 | 只填充用到的表格记录 | 从第一项开始，顺序填满所有表格记录 |
一般来说，如果所有的子问题都至少需要解决一次，那么自底向上的表格法要比记忆表法快；如果某些子问题是不需要被解决的，记忆表法就更有优势。
总结一下，首先我们要判断一个问题是否为动态规划问题，之后我们要用最少的参数来表示状态，然后确定状态转移方程和边界条件，最后（在递归实现的基础上）用记忆表法或者表格法求解。
笔记就整理到这里了，之后拿具体的题目练习吧。
2019年04月03日
网友评论