1 / 106
文档名称:

6 动态规划.ppt

格式:ppt   页数:106页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

6 动态规划.ppt

上传人:cjrl214 2015/6/5 文件大小:0 KB

下载得到文件列表

6 动态规划.ppt

相关文档

文档介绍

文档介绍:动态规划
历史不会重演
引言
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

最近更新

2025年广西现代职业技术学院单招职业倾向性测.. 66页

2025年广西培贤国际职业学院单招职业适应性考.. 64页

超市商品管理要点十则 7页

2025年广西信息职业技术学院单招职业倾向性考.. 65页

2025年广西体育高等专科学校单招职业技能考试.. 63页

2025年广州科技贸易职业学院单招职业技能测试.. 66页

2025年广州民航职业技术学院单招职业技能测试.. 65页

2025年广州城建职业学院单招职业技能考试题库.. 66页

c-学生信息管理系统实验报告 47页

2025年广州体育职业技术学院单招综合素质考试.. 63页

2025年平顶山文化艺术职业学院单招职业适应性.. 67页

2025年嵩山少林武术职业学院单招职业适应性测.. 64页

幼儿园小班社会教案 10页

四川地区汉墓出土鸡俑研究 8页

2025年山西通用航空职业技术学院单招职业适应.. 65页

功能对等理论指导下社科类文本中名词化结构的.. 7页

农村互助养老服务协同供给困境及对策研究 10页

优化活性层材料制备方法构建高性能有机光伏器.. 9页

2025年山西财贸职业技术学院单招职业技能考试.. 65页

COF衍生材料的制备及其电催化性能的研究 9页

房颤患者对出血风险评估 29页

各种常见引流管的护理-PPT 36页

伊利乳业纯牛奶工艺流程图 4页

水利工程中隧洞固结灌浆施工技术分析 32页

牌匾施工方案 26页

牌匾规范施工方案 10页

年产15万吨环己醇工艺设计【完整版】 37页

粗盐提纯除去可溶性杂质课件 19页

西田龙雄:关于十六世纪西康省藏语天全方言—.. 92页

起重机试运转检验记录 1页