斐波那契数列和动态规划 _斐波那契数列

斐波那契数列是数字序列, 其中每个下一个项目是前两个项目的总和。斐波那契数列的每个数字称为斐波那契数。
例如：0, 1, 1, 2, 3, 5, 8, 13, 21, … … … … … … … .是斐波那契数列。
【斐波那契数列和动态规划】斐波那契数F_nare定义如下：

F0 = 0Fn=1Fn=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递归调用, 可以通过写下递归调用的结论并在以后需要时再次查找来避免这种不必要的重复。此过程称为记忆。
这是带有记忆的算法