以计算斐波那契数列为例说说动态规划算法(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集)
相关文章
- 算法思想__动态规划
- Hdoj 1176 免费馅饼 【动态规划】
- 【BZOJ5019】[SNOI2017]遗失的答案(FWT,动态规划)
- 【CF248E】Piglet's Birthday(动态规划)
- 【算法】【递归与动态规划模块】逻辑表达式组成期望结果的所有种数计算
- 【算法】【递归与动态规划模块】两个字符串的公共最长子序列
- 【算法】【递归与动态规划模块】换钱的种数问题
- 【BZOJ2402】陶陶的难题II 分数规划+树链剖分+线段树+凸包
- 【蚁群路径规划】基于MATLAB的蚁群算法的二维路径规划
- C#,人工智能,机器人,路径规划,ARA*(Anytime Replanning A* Algorithm)算法与源程序
- C#,动态规划(DP)丢鸡蛋问题(Egg Dropping Puzzle)的三种算法与源代码
- Redis开发运维实践上线部署规划之内存规划
- 动态规划算法之0-1背包问题
- 强化学习代码实战-03动态规划算法(冰壶游戏测试)
- 【codevs1014/1068】背包型动态规划
- PRM路径规划算法
- 让融合发挥效益:理解CI及企业规划
- 191、【动态规划】AcWing —— 900. 整数划分:完全背包解法+加减1解法(C++版本)
- 183、【动态规划】leetcode ——516. 最长回文子序列(C++版本)
- 180、【动态规划】leetcode ——583. 两个字符串的删除操作:两种动态规划思路(C++版本)
- 130、【贪心算法/动态规划】leetcode ——122. 买卖股票的最佳时机 II(C++版本)
- 【算法/动态规划/股票问题】题解+详细备注(共6题)
- 算法基础复盘笔记Day10【动态规划】—— 线性DP
- 华为OD机试 - 高效的任务规划(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 高效的任务规划(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 秒懂算法 | 子集树模型——0-1背包问题的回溯算法及动态规划改进
- nyoj 36-最长公共子序列 (动态规划,DP, LCS)