文档介绍：动态规划
历史不会重演
引言
F(n) =
1 if n = 0 or 1
F(n-1) + F(n-2) if n > 1
n
0
1
2
3
4
5
6
7
8
9
10
F(n)
1
1
2
3
5
8
13
21
34
55
89
递归算法的伪代码:
F(n)
1 if n=0 or n=1 then return 1
2 else return F(n-1) + F(n-2)
i序列F(n)
2
计算F(7)
F7
F6
F5
F5
F4
F3
F3
F2
F1
F0
F2
F1
F0
F1
F2
F1
F0
F2
F1
F0
F2
F1
F0
F4
F4
F3
F3
F3
F2
F1
F0
F2
F1
F0
F2
F1
F0
F1
F1
F1
F1
3
计算F(7)
计算F(2)重复8次!
F7
F6
F5
F5
F4
F3
F3
F2
F1
F0
F2
F1
F0
F1
F2
F1
F0
F2
F1
F0
F2
F1
F0
F4
F4
F3
F3
F3
F2
F1
F0
F2
F1
F0
F2
F1
F0
F1
F1
F1
F1
4
The execution of F(7)
计算 F(3) 重复 5 次!
F7
F6
F5
F5
F4
F3
F3
F2
F1
F0
F2
F1
F0
F1
F2
F1
F0
F2
F1
F0
F2
F1
F0
F4
F4
F3
F3
F3
F2
F1
F0
F2
F1
F0
F2
F1
F0
F1
F1
F1
F1
5
计算 F(7)
多次重复计算!!
如何避免?
F7
F6
F5
F5
F4
F3
F3
F2
F1
F0
F2
F1
F0
F1
F2
F1
F0
F2
F1
F0
F2
F1
F0
F4
F4
F3
F3
F3
F2
F1
F0
F2
F1
F0
F2
F1
F0
F1
F1
F1
F1
6
改进的想法
备忘录
当 F1(i)被计算后,保存它的值
当再次计算F1(i)时,只需要从内存中取出即可
F1(n)
1 if v[n] < 0 then
2 v[n] ←F1(n-1)+F1(n-2)
3 return v[n]
Main()
1 v[0] = v[1] ←1
2 for i ← 2 to n do
3 v[i] = -1
4 output F1(n)
7
再计算F(7)
1
1
-1
-1
-1
-1
-1
-1
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
F7
F6
F5
F5
F4
F3
F3
F2
F1
F0
F2
F1
F0
F1
F2
F1
F0
F2
F1
F0
F2
F1
F0
F4
F4
F3
F3
F3
F2
F1
F0
F2
F1
F0
F2
F1
F0
F1
F1
F1
F1
F(i)=Fi
8
再计算F(7)
1
1
-1
-1
-1
-1
-1
-1
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
F7
F6
F5
F5
F4
F3
F3
F2
F1
F0
F2
F1
F0
F1
F2
F1
F0
F2
F1
F0
F2
F1
F0
F4
F4
F3
F3
F3
F2
F1
F0
F2
F1
F0
F2
F1
F0
F1
F1
F1
F1
9
再计算F(7)
1
1
2
-1
-1
-1
-1
-1
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
F7
F6
F5
F5
F