介绍
就是一串有规律的数字：
0，1，1，2，3，5，8，13，21，34，55
规律只有一句话：后面的数 = 前面两个数相加
正式写法
设第 n 个数是 F(n)
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2)
就是：
当前数 = 前一个数 + 前前一个数
例子
- 第0个数：0
- 第1个数：1
- 第2个数：0+1 = 1
- 第3个数：1+1 = 2
- 第4个数：1+2 = 3
- 第5个数：2+3 = 5
- 第6个数：3+5 = 8
……
为什么重要？
因为它是讲分治、动态规划最经典的例子：
- 用分治（递归）：重复算很多次，很慢
- 用动态规划：只算一遍，存起来，很快