算法设计与分析动态规划ppt课件.ppt

《算法设计与分析动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划历史不会重演6.1引言F(n)=1ifn=0or1F(n-1)+F(n-2)ifn>1n012345678910F(n)1123581321345589递归算法的伪代码:F(n)1ifn=0orn=1thenreturn12elsereturnF(n-1)+F(n-2)考虑Fibonacci序列F(n)2计算F(7)F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F13计算F(7)计算F(2)重

2、复8次!F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F14TheexecutionofF(7)计算F(3)重复5次!F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F15计算F(7)多次重复计算!!如何避免?F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F

3、2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F16改进的想法备忘录当F1(i)被计算后,保存它的值当再次计算F1(i)时,只需要从内存中取出即可F1(n)1ifv[n]<0then2v[n]←F1(n-1)+F1(n-2)3returnv[n]Main()1v[0]=v[1]←12fori←2tondo3v[i]=-14outputF1(n)7再计算F(7)11-1-1-1-1-1-1v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]F7F6F5F5F4F3F3F2

4、F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1F(i)=Fi8再计算F(7)11-1-1-1-1-1-1v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F19再计算F(7)112-1-1-1-1-1v[0]v[1]v[2]v[3]v[4]v[5]v[6]v

5、[7]F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F110再计算F(7)112-1-1-1-1-1v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F111再计算F(7)1123-1-1-1-1v[0]v[1]v[2]v[3]v

6、[4]v[5]v[6]v[7]F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F112再计算F(7)1123-1-1-1-1v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F113F1F0再计算F(7)11235-1-1-1v[0

7、]v[1]v[2]v[3]v[4]v[5]v[6]v[7]F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F114F1F0F2F1F0F1再计算F(7)11235-1-1-1F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]15F1F0F2F1F0F1再计算F

8、(7)112358-1-1F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]16F1F0F2F1F0F2F1F0F2F1F0F3F1F1再计算F(7)112358-1-1F7F6F5F5F4F3F3F2F1F0F2F1F