斐波那契数列
描述
??大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足
的数列。
数据范围：1≤n≤40
要求：空间复杂度 O(1)，时间复杂度 O(n) ，本题也有时间复杂度 O(logn) 的解法
示例1
输入：
4
返回值：
3
说明：
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。
示例2
输入：
1
返回值：
1
示例3
输入：
2
返回值：
1
思路/解法
方式一
递归求解。
class Solution {
public:
int Fibonacci(int n) {
if(n == 1 || n == 2)return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
};
方式二
使用数组求解。
class Solution {
public:
int Fibonacci(int n) {
vector<int> arr(n);
arr[0] = 1;
arr[1] = 1;
for(int i = 2;i < n;i++)
arr[i] = arr[i-1] + arr[i-2];
return arr[n-1];
}
};
方式三
不使用数组这类额外空间求解。
class Solution {
public:
int Fibonacci(int n) {
if(n == 1 || n == 2)return 1;
int a = 1;
int b = 1;
int c = a + b;
for(int i = 3;i < n;i++)
{
a = b;
b = c;
c = a + b;
}
return c;
}
};
