以计算斐波那契数列为例说说动态规划算法(Dynamic Programming Algorithm Overlapping subproblems Optimal substructure Memoization Tabulation)

动态规划(Dynamic Programming)是求解决策过程(decision process)最优化的数学方法。它的名字和动态没有关系,是Richard Bellman为了唬人而取的。

动态规划主要用于解决包含重叠子问题的最优化问题,其基本策略是将原问题分解为相似的子问题,通过求解并保存重复子问题的解,然后逐步合并成为原问题的解。动态规划的关键是用记忆法储存重复问题的答案,避免重复求解,以空间换取时间。

用动态规划解决的经典问题有:最短路径(shortest path),0-1背包问题(Knapsack problem),旅行商人问题(traveling sales person)等等。

(注:背包问题分为两种:若物体不可分割,则称为0-1背包问题,比如拿一块金砖;若物体可以分开,则称为一般背包问题,比如拿多少克大米。一般背包问题可以用贪心算法解决。贪心算法在每个阶段即可找出当前最优解,每个阶段的最优状态都是由上一个阶段的最优状态得到的。)

可以采用动态规划来求解的问题需要具有以下两个主要特征:

1)重叠子问题(Overlapping Subproblems):有些子问题会被重复计算多次。

2)最优子结构(Optimal Substructure):问题的最优解可以从某个子问题的最优解中获得。

 

下面以计算斐波那契数列为例,看看动态规划算法的实现过程。

以下是1-5的斐波那契数列递归树:

                         fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ ¦ ¦ ¦
fib(2) fib(1) 1 1 1
¦ ¦
1 1

可以看出,fib(5)是由fib(4)和fib(3)相加而成,fib(4)则是由fib(3)和fib(2)相加而成,等等。其中,fib(3)要计算2次,fib(2)要计算3次。这里面进行了很多重复的计算。

按之前博客中提到的递归方法来计算这个斐波那契数列(用递归方法计算斐波那契数列),在此基础上加入print("fib called with",n)语句后,看看fib函数的调用情况:

def fib(n):
print("fib called with",n) #看调用了哪个fib函数,也就是说看计算了斐波那契数列的第几项
if n<2:
return n
else:
return (fib(n-1) + fib(n-2))

计算一下斐波那契数列的第5项试试:

print(fib(5))

运行结果如下:

fib called with 5
fib called with 4
fib called with 3
fib called with 2
fib called with 1
fib called with 0
fib called with 1
fib called with 2
fib called with 1
fib called with 0
fib called with 3
fib called with 2
fib called with 1
fib called with 0
fib called with 1
5

可以看出一共进行了15次调用,其中fib(3)被计算了2次,fib(2)被计算了3次。

而使用动态规划算法来计算这个斐波那契数列,运行则会快一些。代码如下:

def fastFib(n,memo):  #memo是设置的一个字典
print("fib1 called with",n)
if not n in memo: #如果斐波那契数列的第n项数值不在字典里,那么用递归方式计算该值,并把该值放入字典中
memo[n]=fastFib(n-1,memo)+fastFib(n-2,memo)
return memo[n] #如果斐波那契数列的第n项数值在字典里,那么直接返回字典里的该项数值 def fib1(n):
memo={0:0,1:1} #初始化一个字典
return fastFib(n,memo)

同样也计算一下斐波那契数列的第5项试试,运行结果如下:

fib1 called with 5
fib1 called with 4
fib1 called with 3
fib1 called with 2
fib1 called with 1
fib1 called with 0
fib1 called with 1
fib1 called with 2
fib1 called with 3
5

可以看出一共进行了9次调用,在进行过一次计算之后,后面的调用都是直接到字典里去获取该值即可。

有两种不同的方式来存储数值:

1) 默记法(从上到下)/ Memoization (Top Down):设置一个数组,当需要子问题的解时,先去这个数组中查找。如果此问题之前已经求过解,那么就直接返回该值,如果此问题之前并未求过解,那么就计算该值并把结果放入数组中,以备后用。

2) 表格法(从下到上)/ Tabulation (Bottom Up):用迭代法建立一个表格,从该表格中返回所需的值。

那么到底应该用默记法还是表格法呢?

如果需要求解所有的子问题,那么表格法往往要比默记法好。这是因为表格法没有递归的额外消耗,并且使用预先分配好的数组(preallocated array),而不是哈希图(hash map)。

如果只是需要求解其中一些子问题,那么默记法则要好些。

参考:麻省理工学院公开课:计算机科学及编程导论(第13集)

上一篇:[项目回顾]基于Annotation与SpringAOP的缓存简单解决方案


下一篇:Python学习笔记——基础篇2【第三周】——计数器、有序字典、元组、单(双)向队列、深浅拷贝、函数、装饰器