第一次开始写笔记，以前也不知道刷题，也不知道写笔记，废话不多说，领扣上的入门级题目斐波纳契数列

查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
第一次头铁直接写，上了递归，然后华丽的超时了（笑）
代码如下
int fibonacci(int n) {
if(1==n)
return 0;
if(2==n)
return 1;
int result;
result =fibonacci(n-1)+fibonacci(n-2);
return result;
}
然后想了一下学聪明了，用个数组存起来已经计算出来的数不行吗
新知识点来了划重点
用static初始化数组可使得数组只被定义一次之后递归调用的时候可以修改，但不会重复定义
int fibonacci(int n) {
static int temresult[100] = { -1 };
temresult[1] = 0;
temresult[2] = 1;
if (1 == n)
return 0;
if (2 == n)
return 1;
int result,a1,a2;
if (-1==temresult[n-1])
{
temresult[n - 1] = fibonacci(n - 1);
}
if (-1 == temresult[n - 2])
{
temresult[n - 2] = fibonacci(n - 2);
}
result = temresult[n - 1] + temresult[n - 2];
return result;
}
以为这就完了，不，问题又出来了，错的还是最基本的。
static int temresult[100] = { -1 };
就是这一行数组的定义错误，这样定义只会吧最开始的元素变为-1而编译器会把其余其他99个元素自动定义为0
没办法，改吧
既然这里面要求的数据含零和数组的自动定于冲突，那就给他弄个标记数组visited[100]来记录这个有没有算过，代码如下
int fibonacci(int n) {
static int temresult[100] = { 0 };
static int visited[100] = { 0 };
temresult[1] = 0;
temresult[2] = 1;
if (1 == n)
return 0;
if (2 == n)
return 1;
int result,a1,a2;
if (0==visited[n-1])
{
temresult[n - 1] = fibonacci(n - 1);
visited[n - 1] = 1;
}
if (0 ==visited[n - 2])
{
temresult[n - 2] = fibonacci(n - 2);
visited[n - 2] = 1;
}
result = temresult[n - 1] + temresult[n - 2];
return result;
}
然后我又发现了这跟之前接触到的一个东西很像——动态规划的走楼梯种类
具体可以看一下这个网址上的漫画
http://www.sohu.com/a/153858619_466939
稍微加点解释吧，不想看上面的网址的话，也能快速了解
f（n）=f（n-1）+f（n-2）
以及边界条件
f（1）=0，f（2）=1
可以模拟自下而上的计算，n是几就计算n-2遍
那么我们可以用三个变量a，b，result 来分别储存：结果（f（n）），以及之前的两个相加的量（f（n-1）和f（n-2））
对变量进行这样的处理就可以让a一直等于f（n-1）而b一直等于f（n-2）
result = a + b;//即是f（n）=f（n-1）+f（n-2）
a=b;
b = result;
——————————————————————————
总的代码如下
int fibonacci(int n) {
int result,a=0,b=1;
if (1==n)
return 0;
if (2 == n)
return 1;
for (int i = 0; i < n-2; i++)
{
result = a + b;//即是f（n）=f（n-1）+f（n-2）
a=b;
b = result;
}
return result;
}