描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。
n\leq 39n≤39
示例1
输入:
4
复制
返回值:
3
1、递归:效率低下
class Solution {
public:int Fibonacci(int n) {if (n == 0) {return 0;} if (n == 1) {return 1;}return Fibonacci(n - 1) + Fibonacci(n - 2);}
};```2、迭代法 最喜欢```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];}
};