斐波那契数列和动态规划

斐波那契数列是数字序列, 其中每个下一个项目是前两个项目的总和。斐波那契数列的每个数字称为斐波那契数。

例如：0, 1, 1, 2, 3, 5, 8, 13, 21, ………………….是斐波那契数列。

斐波那契数F_nare定义如下：

F0 = 0
Fn=1
Fn=F(n-1)+ F(n-2)

FIB (n) 
 1. If (n < 2) 
 2. then return n 
 3. else return FIB (n - 1) + FIB (n - 2)

图：显示了调用fib（8）的四个递归级别：

图：计算斐波那契数期间的递归调用

对fib（n）的单个递归调用将导致对fib（n-1）的一个递归调用, 对fib（n-2）的两个递归调用, 对fib（n-3）的三个递归调用, 对fib（五个）的递归调用n-4）, 以及通常对fb（n-k）的Fk-1递归调用, 可以通过写下递归调用的结论并在以后需要时再次查找来避免这种不必要的重复。此过程称为记忆。

这是带有记忆的算法

MEMOFIB (n)
 1 if (n < 2) 
 2 then return n
 3 if (F[n] is undefined)
 4 then F[n] ← MEMOFIB (n - 1) + MEMOFIB (n - 2)
 5 return F[n]

如果我们跟踪对MEMOFIB的递归调用, 则会发现数组F []从下往上填充。即, 首先是F [2], 然后是F [3], 依此类推, 直到F [n]。我们可以用简单的for循环替换递归, 该循环仅按顺序填充数组F []

ITERFIB (n) 
 1 F [0] ← 0 
 2 F [1] ← 1 
 3 for i ← 2 to n 
 4 do 
 5 F[i] ← F [i - 1] + F [i - 2] 
 6 return F[n]

该算法显然只需要O（n）时间来计算Fn。相比之下, 原始的递归算法取O（∅n;）, ∅= = 1.618。 ITERFIB得出了原始递归算法的指数加速的结论。