动态规划 - Dynamic Programming

Those who cannot remember the past are condemned to repeat.

-Dynamic Programming

今天的算法课讲的就是动态规划,虽早已久仰大名,但始终不太懂背后原理。听完课后赶紧把今天学到的东西记下来。

动态规划和分治法有类似之处,他们都是通过组合子问题的解来求解原问题。不同之处在于,分治法常常用于将原问题划分为几个互不相交的子问题,如果划分后,有很多完全相同的子问题,那就使用动态规划的思路比较好。例如快速排序,将一段数组以枢纽值为界一分为二,再将这两段分别排序。将分出来的两段数组分别排序就是互不相交的两个子问题,可以使用分治法来解决。再如求斐波那契数列的第n项问题,我们知道斐波那契数列的规律是
$$
F(0) = 0 \quad F(1) = 1 \quad F(n) = F(n - 1) + F(n - 2) (n >= 2)
$$
我们发现求F(n)需要计算F(n-1)和F(n-2),可是当计算F(n-1)和F(n-2)时,都需要计算F(n-3),这样就造成了重复计算,大幅降低了效率,而动态规划算法的目的就是避免此类重复计算。

去年暑假,我好好思考了一下上台阶问题:

有100级台阶,每次只允许上1级台阶或上2级台阶,若要求上完全部台阶,共有多少种上法?

第一次看到还以为是组合数学问题,后来也没做出来。再一想,要不直接枚举吧,那这样的数据规模是惊人的,是指数级的时间复杂度。

emmm~我们考虑一下分治法吧。假设一下,现在已经站在了第100层台阶上,回忆一下刚刚最后一步我是怎么上来着的。我最后一步可以是从98层一步跨上来的,也可以是从99层踩上一级台阶上来。这时让我们时光倒流,我们可以选择最后一步从98层跨两级上来,也可以选择从99层爬一级上来。

现在我们将这两种可能分开讨论,如果我限定最后一步只能走一步,那么之前我就必须上到99层,而99层到100层只有1条路可走,上到100层的上法就等于上到99层的上法,所以我现在只要得知上到99层有多少种上法,就知道了上到100层有多少种上法;同理,如果我限定最后一步必须跨两步,那么我之前就必须上到98层,所以我现在只要得知上到98层有多少种上法,98层到100层也只有跨两级这一条路,所以上到100层的上法就等于上到98层的上法了。

现实里,最后一步可以跨两级,也可以只爬一级,所以上到100层的上法,应该等于上到98层的上法加上上到99层的上法。如果用函数F(n)表示上到第n层一共有多少种上法,那么就有F(100) = F(99) + F(98),接下来也有F(99) = F(98) + F(97),F(98) = F(97) + F(96)……。

这样问题就很简单了,只要这样不断递归下去,总会递归到一个终点,这个终点就是F(1)和F(2),上一层台阶有多少种上法呢,显然除了一步跨上去没别的方法了吧,所以F(1) = 1;上两层台阶呢?一步一步爬,或是一步跨两个,F(2)应该等于2。那么现在的递归式应该是:
$$
F(1) = 1 \quad F(2) = 2 \quad F(n) = F(n - 1) + F(n - 2) (n > 2)
$$
将n取值为100,这样我们就可以算出结果了,用c++写出的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

long F(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
return F(n - 1) + F(n - 2);
}
}

int main() {
long result = F(100);
cout << result;
return 0;
}

这个代码跑很久都是跑不出来的,就是因为重复计算的部分太多了,详细讲来,如果我们要算f(100),那么我们需要先得知f(99)和f(98),然后想要得知f(99)和f(98),都需要先算出f(97),这样f(97)就计算了两遍,造成了重复计算,浪费了大量时间。上面代码中包含大量重复计算的内容,而动态规划算法就很好的解决了重复计算的问题。

现在我们不再从100层开始逐层向下递归,而是从第一层开始逐层向上走。什么意思呢?正如上面提到的问题,如果从下往上计算的话,我们先算出了f(97)的值,然后在计算f(99)和f(98)的时候,就可以共享一个计算成果,不需要花两倍的时间来计算。

从底层开始计算时,我们首先得知f(1) = 1以及f(2) = 2,根据F(n) = F(n - 1) + F(n - 2)的公式,可以很轻松算出F(3) = 3,F(4) = 5,然后继续向下推,直到n到100就可以得到结果。用代码实现的话,可以新开一个数组array,array[n]内存储了F(n)的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;

long F(int n) {
vector<long> array(n + 1, 0);
array[1] = 1;
array[2] = 2;

for (int i = 3; i <= n; i++)
array[i] = array[i - 1] + array[i - 2];

return array[n];
}

int main() {
long result = F(100);
cout << result;
return 0;
}

这里只需要一个循环就可以得出结果啦~这个代码的时间复杂度是O(n),但是我们的空间复杂度也达到了O(n),我们发现很多数据都是只使用了一次就不再使用了,将这个数组改为3个变量循环交替使用可以加大使用效率。

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
#include <iostream>
#include <vector>
using namespace std;

long F(int n) {
long A, B, C;
A = 1;
B = 2;

if (n == 1) return A;
else if (n == 2) return B;
else {
for (int i = 3; i <= n; i++) {
C = A + B;
A = B;
B = C;
}
return C;
}
}

int main() {
long result = F(100);
cout << result;
return 0;
}

我们使用3个变量ABC交替使用,只要始终保持ABC的先后顺序就可以啦!这种方法还将空间复杂度降为了O(1)。当然这题我们发现刚好是求斐波那契数列的第101项,如果我们直接使用斐波那契数列求第n项公式可以在常数级的时间内求出结果,但那和动态规划没有关系啦~

总结一下:线性规划就是先用分治法的方法,从终点往前思考,用递归的方式定义解;然后我们发现其中有很多重复的子问题,这样我们又从起点开始,逐步记录已经求好的子问题的解,然后需要时再拿出来用,以此节约时间。




======================
全文结束 硬币要投
你投币 你就是 我的大舅!
======================