LeetCode21：深入解析斐波那契数列算法挑战

题目要求
  大家都知道斐波那契数列&＃xff0c;现在要求输入一个整数n&＃xff0c;请你输出斐波那契数列的第n项&＃xff08;从0开始&＃xff0c;第0项为0&＃xff0c;第1项是1&＃xff09;。
思路
  1. 采用递归的思想。
  2. 采用动归的思想。
    问题&＃xff1a;数列第n项的值
    状态F(i)&＃xff1a;数列第i项的值
    转移方程:F(i) &＃61; F(i-1) &＃43; F(i-2)
    初始状态:F(0) &＃61; 0, F(1) &＃61; 1
    返回&＃xff1a;F(n)
  3. 采用循环&＃xff0c;存储每一次的中间值&＃xff0c;为下一次的计算做准备。

代码实现
思路1.

class Solution {
public:int Fibonacci(int n) {if(n &＃61;&＃61; 0){return 0;}if(n &＃61;&＃61; 1 || n &＃61;&＃61; 2){return 1;}return Fibonacci(n-1)&＃43;Fibonacci(n-2);}
};


思路2.

class Solution {
public:int Fibonacci(int n) {vector F(n &＃43; 1, 0);//初始化F[1] &＃61; 1;for (int i &＃61; 2; i <&＃61; n; i&＃43;&＃43;){F[i] &＃61; F[i - 1] &＃43; F[i - 2];}return F[n];}
};


思路3.

class Solution {
public:int Fibonacci(int n) {int f2 &＃61; 0;int f1 &＃61; 1;int f;if (n <&＃61; 1){return n;}for (int i &＃61; 2; i <&＃61; n; i&＃43;&＃43;){f &＃61; f1 &＃43; f2;f2 &＃61; f1;f1 &＃61; f;}return f;}
};