剑指offer10斐波那契数列（递归、迭代、记忆化、数组四种方法）

描述
大家都知道斐波那契数列&＃xff0c;现在要求输入一个整数n&＃xff0c;请你输出斐波那契数列的第n项&＃xff08;从0开始&＃xff0c;第0项为0&＃xff0c;第1项是1&＃xff09;。
n\leq 39n≤39
示例1
输入&＃xff1a;
4
复制
返回值&＃xff1a;
3

1、递归&＃xff1a;效率低下

class Solution {
public:int Fibonacci(int n) {if (n &＃61;&＃61; 0) {return 0;} if (n &＃61;&＃61; 1) {return 1;}return Fibonacci(n - 1) &＃43; Fibonacci(n - 2);}
};&＃96;&＃96;&＃96;2、迭代法 最喜欢&＃96;&＃96;&＃96;cpp
class Solution {
public:int Fibonacci(int n) {if (n &＃61;&＃61; 0) {return 0;} if (n &＃61;&＃61; 1) {return 1;}int fistNumber &＃61; 0;int SecondNumber &＃61; 1;int result &＃61; 0;for (int i &＃61; 2; i <&＃61; n; i&＃43;&＃43;) {result &＃61; SecondNumber &＃43; fistNumber;fistNumber &＃61; SecondNumber;SecondNumber &＃61; result;}return result;}
};&＃96;&＃96;&＃96;3、动态规划&＃xff0c;用个数组保存&＃xff0c;但是需要额外的空间&＃96;&＃96;&＃96;cpp
class Solution {
public:int Fibonacci(int n) {if (n &＃61;&＃61; 0) {return 0;} if (n &＃61;&＃61; 1) {return 1;}vector<int> result(n &＃43; 1);result[0] &＃61; 0;result[1] &＃61; 1;for (int i &＃61; 2; i <&＃61; n; i&＃43;&＃43;) {result[i] &＃61; result[i - 1] &＃43; result[i - 2];}return result[n];}
};


4、记忆化数组&＃xff0c;复杂&＃xff0c;也不快啊

class Solution {
public:int Fibonacci(int n) {if (n &＃61;&＃61; 0) {return 0;} if (n &＃61;&＃61; 1) {return 1;}vector<int> result(n &＃43; 1);result[0] &＃61; 0;result[1] &＃61; 1;for (int i &＃61; 2; i <&＃61; n; i&＃43;&＃43;) {result[i] &＃61; result[i - 1] &＃43; result[i - 2];}return result[n];}
};