Download presentation
Presentation is loading. Please wait.
1
动态规划(Dynamic Programming)
2
1. 什么是动态规划？
3
Fibonacci序列 Fibonacci序列被定义如下： F(n) = F(n - 1) + F(n - 2), n≥ 3
问题：如何计算第n个Fibonacci数F(n)?
4
算法1 F(1) = 1 F(2) = 1 F(n) = F(n - 1) + F(n - 2), n≥ 3 F(n)
if (n == 1) return 1; if (n == 2) return F(n - 1) + F(n - 2);
5
算法1的效率 F(n) if (n == 1) return 1; if (n == 2)
return F(n - 1) + F(n - 2);
6
算法1的效率 F(n) if (n == 1) return 1; if (n == 2)
return F(n - 1) + F(n - 2); 目标：计算F(100)。 问题：在计算F(100)的过程中， F(99)被调用(计算)多少次？ F(98)被计算多少次? … … F(3)被计算多少次?
7
F(100)的执行过程 … …
8
算法2 F(n) Fib[1] = 1; Fib[2] = 1; for i = 3 to n
Fib[i] = Fib[i – 1] + Fib[i – 2]; return Fib[n]; Fib[1..n]是一维数组, 用Fib[i]来存储F(i)的值。
![算法2 F(n) Fib[1] = 1; Fib[2] = 1; for i = 3 to n](http://slidesplayer.com/slide/15520667/93/images/8/%E7%AE%97%E6%B3%952+F%28n%29+Fib%5B1%5D+%3D+1%3B+Fib%5B2%5D+%3D+1%3B+for+i+%3D+3+to+n.jpg "Fib[i] = Fib[i – 1] + Fib[i – 2]; return Fib[n]; Fib[1..n]是一维数组, 用Fib[i]来存储F(i)的值。")
9
算法1 vs 算法2
10
什么是动态规划？ 对于有些问题，解决该问题的过程中需要重复解决该问题的子问题。
动态规划是一种解决此类问题的方法。其核心思想是：“重用子问题的计算结果，避免重复计算”。
Similar presentations
