动态规划

Dynamic Programming (动态规划)

动态规划是解决随“时间”演变的问题的一种程序设计方法。

实际生活中,待解决的问题随时间变化是一个很正常的事情。

动态规划实际上就是在程序中动态地分析问题、解决问题的技术。

动态规划:人类 vs 计算机

动态规划是一种典型的,从人的行为中抽象出来的设计方法。

人类可以即时地分析问题,不限于已知的模式,但模拟演算能力不足,而且个体思维能力差异很大。

计算机模拟演算的能力强大,但只能根据给定的模式分析问题。

关于人类是如何进行动态规划的,参考运筹学:动态规划相关篇目,本文不作更多探讨。

计算机目前依然不具备自主创新的能力,因此只能按照人类设定的模式分析问题。

因此通常情况下,它要求将既有问题规约成已有类型的问题,而且要求问题的“规模”严格降低。

所以,动态规划与递归从设计方法上是一致的。

动态规划算法设计的阶段

  1. 分析问题的规约性质

    写出所谓的“状态转移方程”。

  2. 决定计算顺序

    给出计算的拓扑序。

    更一般地,用拓扑排序来决定?

    若不存在拓扑序,则这个问题是具有后效性的,不适用动态规划

以上两步可以确定一个合法的动态规划解,而且这个解的时间复杂度也会被确定,还会对这个解的空间复杂度形成约束

同一个问题可能具备多种“状态转移方程”,计算顺序也是可变的。

所以还需要探究最优解法,这个过程称为优化

动态规划算法的优化大致分为两种:优化时间复杂度、优化空间复杂度。

暂时不考虑编程复杂度,因为没有对应的理论出现。

优化时间复杂度通常着眼于状态转移方程的变换

优化空间复杂度通常着眼于及时重用存储空间

引导案例:Fibonacci

问题背景

求 Fibonacci 数的问题可以说是很常见了,根据定义:
$$
f(n) = \begin{cases}
1 & 0 \le n < 2 \
f(n - 1) + f(n - 2) & n \ge 2
\end{cases}
$$

1
2
3
4
5
// #1: Naive Fibonacci Implementation (Recursive)
int f(int n) {
if (n < 2) return 1;
return f(n - 1) + f(n - 2);
}

这是一个最简单的递归实现,也可以手写个栈转化成一个迭代版本模拟递归(不是重点,可以跳过):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// #2: Naive Fibonacci Implementation (Iterative)
const int MAXS = 50; // maximum stack size
int s_f_arg1[MAXS]; // stack for the 1st argument of function 'f'
int s_f_pc[MAXS]; // stack for PC of function 'f'
int s_f_temp1[MAXS]; // stack for the temp value (f(n - 1)) of function 'f'
int ret; // register of return value
int f(int n) {
int top = 0; // call fibonacci(n)
s_f_arg[top] = n;
s_f_pc[top] = 0;
while (top >= 0) {
switch (s_f_pc[top]) {
case 0:
if (s_f_arg1[top] < 2) { // if n < 2
ret = 1;
top--;
} else { // call fibonacci(n - 1)
s_f_arg1[top + 1] = s_f_arg1[top] - 1;
s_f_pc[top + 1] = 0;
s_f_pc[top]++; // store pc
top++;
}
break;
case 1:
s_f_temp1[top] = ret; // store fibonacci(n - 1)
// call fibonacci(n - 2)
s_f_arg1[top + 1] = s_f_arg1[top] - 2;
s_f_pc[top + 1] = 0;
s_f_pc[top]++; // store pc
top++;
break;
case 2:
ret = s_f_temp1[top] + ret;
top--;
break;
}
}
return ret;
}

上面这两个代码是等价的(忽略 MAXS 的值)。

人力转换递归迭代十分具有挑战性,将递归转换为迭代要考虑几个要点:保存局部变量、保存程序运行的位置、返回值的处理。

上面的例子可以揭示为什么递归过深会爆栈。

动态规划解法

DP 的一个重要的设计哲学就是复用问题的解,显然上述代码并没有做到这一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// #3: Naive Memorize Fibonacci Implementation (Recursive)
int c_f[50]; // cache for function 'f'
bool c_f_valid[50]; // cache validation for function 'f'
int f(int n) {
if (c_f_valid[n]) { // check cache
return c_f[n];
}
int ans;
if (n < 2) {
ans = 1;
} else {
ans = f(n - 1) + f(n - 2);
}
c_f[n] = ans; // memorize
c_f_valid[n] = true;
return ans;
}

我们需要一些空间来存储这些已经被求过的解,对比代码 #1#3 ,实际上只是加了一个检查缓存(cache)以及记录缓存的代码。

然后这个速度突然就比之前的代码 #1#2 高到不知道哪里去了,因为对于需要的问题,只计算了一次,之后需要的时候都在复用答案。

为什么缓存答案是正确的?

这依赖于问题的“无后效性”性质,此处初次引出,之后详细讨论。

对于先计算 f(n) 后计算 f(m) ,f(n) 的结果不随 f(m) 发生改变。

例如 f(2) 的值与 f(3) 无关。

有效性与结果的调制/解调

观察 Fibonacci 函数的值域,发现最小值是0,那么 -1 必然不是解,因此我们可以把 c_fc_f_valid 的信息调制到一起:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// #4: Naive Modal Memorize Fibonacci Implementation (Recursive)
int c_f[50]; // cache for function 'f', init with -1
int f(int n) {
if (c_f[n] >= 0) { // check cache
return c_f[n];
}
int ans;
if (n < 2) {
ans = 1;
} else {
ans = f(n - 1) + f(n - 2);
}
c_f[n] = ans; // memorize
return ans;
}
// call it somewhere only once
void init() {
memset(c_f, -1, sizeof(c_f))
}

这样可以少一次赋值,也能节约一些空间。

基于未定义值(undefined)的空间优化

对于能确定”未定义”值的缓存,可以先将缓存初始化为未定义值,然后检查这个值来确定这个问题是否被计算过。

对于不能确定”未定义”值的问题,就必须使用额外的空间来保存这个问题是否被计算过。

栈深度分析

观察最大递归栈深度,对代码 #4 稍作分析,可以发现最大栈深度 h 与问题规模 n 存在如下关系:
$$
h = n, n \ge 2
$$
例如:计算 f(6) 的时候,调用栈中可能会出现 f(6), f(5), f(4), f(3), f(2), f(1),最多 6 层的深度。

那么我把计算顺序微调一下会如何呢:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// #5: Tricky Modal Memorize Fibonacci Implementation (Recursive)
int c_f[50]; // cache for function 'f', init with -1
int f(int n) {
if (c_f[n] >= 0) { // check cache
return c_f[n];
}
int ans;
if (n < 2) {
ans = 1;
} else {
ans = f(n - 2) + f(n - 1); // CHANGE HERE!
}
c_f[n] = ans; // memorize
return ans;
}
// call it somewhere only once
void init() {
memset(c_f, -1, sizeof(c_f))
}

再考虑 f(6) 的情况,调用栈中可能会出现 f(6), f(4), f(2), f(0),最多 4 层的深度。

综合分析后不难得出一个关于最大栈深度 h 与问题规模 n 的关系:
$$
h = \lceil{\frac{n}{2}}\rceil + 1, n \ge 2
$$
从代码上看只有微小的改动,但节约了几乎一半的栈空间,惊了!

而且从搜索树的层数看,这已经达到了递归方法的极限。

1
2
3
4
5
# BFS: f(6) needs 4 frames of stack at least
f(6)
f(4) f(5)
f(2) f(3)
f(0) f(1)

从此处也可以引出一个问题:

计算顺序对于性能的影响是很大的,如何优化计算顺序?之后详细讨论。

求解拓扑序与迭代形式

然而即便是节约了一半的栈空间,依然有可能栈溢出。能不能再给力一点?很简单,先预计算一遍即可,完全不用改主要代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// #6: Preprocess Tricky Modal Memorize Fibonacci Implementation (Recursive)
int c_f[50]; // cache for function 'f', init with -1
int f(int n) {
if (c_f[n] >= 0) { // check cache
return c_f[n];
}
int ans;
if (n < 2) {
ans = 1;
} else {
ans = f(n - 1) + f(n - 2);
}
c_f[n] = ans; // memorize
return ans;
}
// call it somewhere only once
void init(int n) {
memset(c_f, -1, sizeof(c_f));
for (int i = 0; i <= n; ++i) f(i); // call
}

按顺序预计算一遍这些问题,就可以使得要求的问题的解被全部缓存,而且能保证最大栈深度 h 的最大值是常数 2。

至此,递归造成的栈溢出问题就得到了解决。

但代码#6看上去依然有些繁冗了,而且这样还递归看上去很傻,既然要做这些优化,不如直接在初始化的时候就准备好 c_f 的数据。

至此我们不依赖于语言本身来帮助我们确定计算顺序,而是需要自己考虑全局计算顺序,即该问题的解第一次被计算出来的顺序,也称为计算顺序

在上述代码#1 - #6中,考虑计算顺序,均为:0, 1, 2, …, n 。

这指导我们可以直接按照计算顺序进行计算,即能保证之前的解已经全部有效。

1
2
3
4
5
6
7
8
9
10
11
// #7: Preprocess Fibonacci Implementation (Iterative)
int c_f[50];
void init(int n) {
for (int i = 0; i <= n; ++i) {
if (i < 2) {
c_f[i] = 1;
} else {
c_f[i] = c_f[i - 1] + c_f[i - 2];
}
}
}

看上去 #7 跟基础的递归实现 #1 在编程复杂度上也没有差别了,然而却自带记忆化,时空复杂度都是 $O(n)$ 的水准。

滚动数组

还能不能再给力一点?如果只是一次性的计算,我们还可以尝试优化一下空间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// #8: Scrolling Fibonacci Implementation (Iterative)
int f(int n) {
int c_f[2];
for (int i = 0; i <= n; ++i) {
if (i < 2) {
// map solution storage:
// c_f[i % 2] = 1;
// and because:
// for a non-negative number i, i < 2
// i == i % 2
// so we get:
// c_f[i] = 1;
c_f[i] = 1;
} else {
// map solution storage:
// c_f[i % 2] = c_f[(i - 1) % 2] + c_f[(i - 2) % 2];
// and because:
// i % 2 == (i - 2) % 2
// so we get:
// c_f[i % 2] = c_f[(i - 1) % 2] + c_f[i % 2];
// that is:
// c_f[i % 2] += c_f[(i - 1) % 2];
c_f[i % 2] += c_f[(i - 1) % 2];
}
}
return c_f[n % 2];
}

实际上,如果一个问题的解已经不需要了,那么可以重用存储这个解的空间,上述的代码 #8 就做到了这一点,这是一种称为滚动数组的空间优化。

案例总结

代码编号 时间复杂度 空间复杂度 递归/迭代 最大栈深度 备注
1 $O(a^n)$ $O(n)$ 递归 n 朴素递归解法
2 $O(a^n)$ $O(n)$ 迭代 1 手动栈迭代形式
3 $O(n)$ $O(n)$ 递归 n 记忆化递归解法
4 $O(n)$ $O(n)$ 递归 n 基于3,调制有效信息
5 $O(n)$ $O(n)$ 递归 $\lceil\frac{n}{2}\rceil + 1$ 基于4,优化栈深度
6 $O(n)$ $O(n)$ 递归 2 基于4,预处理
7 $O(n)$ $O(n)$ 迭代 1 基于计算顺序的迭代形式
8 $O(n)$ $O(1)$ 迭代 1 基于7,滚动数组空间优化

在代码 #3 - #8 中,同样是 DP,同样的状态转移方程,同样的计算顺序,因此他们具有一样的时间复杂度 $O(n)$,但空间复杂度等其他性质却不尽相同。

最重要的事情是问题的规约阶段,即求出状态转移方程 $E$;

状态转移方程 $E$ 蕴含了一个依赖关系 $D$;

将 $D$ 作为一个依赖图 $G$,通过拓扑排序可以得到某个 计算顺序 $S$;

而 $(E, S)$ 直接确定了 DP 算法实现的时间复杂度。