1. 题目
🟠 题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。
🟠 基础框架
C++ 版本给出的基础框架代码如下：
class Solution {
public:
int Fibonacci(int n) {
}
};
🟠 原题链接
2. 解题报告
对于斐波那契的求解方法，相信大家不会陌生，我这里给出了三种方法。
🟠 方法一：递归
斐波那契数列的定义：
F
(
n
)
=
F
(
n
−
1
)
+
F
(
n
−
2
)
F(n)=F(n-1)+F(n-2)
F(n)=F(n−1)+F(n−2)
（
n
>
=
2
，
n
∈
N
∗
）
（n>=2，n∈N*）
（n>=2，n∈N∗），其中
F
(
1
)
=
1
，
F
(
2
)
=
1
F(1)=1，F(2)=1
F(1)=1，F(2)=1
代码实现：
class Solution {
public:
int Fibonacci(int n) {
//n小于0,直接返回0
if (n < 0) {
return 0;
}
//第一项和第二项都是1
if (n == 1 || n == 2) {
return 1;
}
// F(n)=F(n-1)+F(n-2)
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
};
🟣 复杂度分析
递归的方法时间复杂度为
O
(
2
n
)
O(2^n)
O(2n)，随着 n 的增大呈现指数增长，效率低下。
当输入比较大时，可能导致栈溢出，而且在递归过程中有大量的重复计算。
n = 5 的时候，Fib(1) 就已经 5 次参与运算，Fib(2) 就已经 3 次参与运算，Fib(3) 被重复计算了 2 次，可想而知，当 n 越变越大时，重复计算的量就会大量增加，计算的速度会随着 n 的增加肉眼可见的变慢，程序甚至会挂。
因此，若是将每次计算出的小问题存起来就可以很好地提高效率，我们可以准备一个数组来存放小问题的结果。
🟠 方法二：动态规划
动态规划的基本方法在第一篇文章中已经说过了，首先我们来看一下分析过程：
（1）状态定义：Fib(i) 的值，即斐波那契数列的第 i 项的值。
（2）状态转移方程：Fib(i) = Fib(i-1) + Fib(i-2)
（3）状态的初始化：Fib(0) = 0，Fib(1) = 1
（4）返回结果：F(n)
代码实现：
class Solution {
public:
int Fibonacci(int n) {
// 初始值
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
// 申请一个数组，保存子问题的解，题目要求从第0项开始
int* record = new int[n + 1];
record[0] = 0;
record[1] = 1;
for (int i = 2; i <= n; i++) {
// F(n)=F(n-1)+F(n-2)
record[i] = record[i - 1] + record[i - 2];
}
return record[n];
delete[] record;
}
};
🟣 复杂度分析
上述解法的时间复杂度为
O
(
n
)
O(n)
O(n)，空间复杂度为
O
(
n
)
O(n)
O(n)
🟠 方法三：动态规划改良
其实 Fib(n) 只与它相邻的前两项有关，所以没有必要保存所有子问题的解，只需要保存两个子问题的解就可以。
所以我们也没必要额外开辟新的空间，我们只需要知道第 n 项的前 2 项值即可，直接定义一个 result 用来在循环的过程中不断更新 n - 1 和 n - 2 为斐波那契数的值即可。
代码示例
class Solution {
public:
int Fibonacci(int n) {
// 初始值
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int fn1 = 1; //第1个数
int fn2 = 1; //第2个数
int ret = 0;
for (int i = 3; i <= n; ++i) {
// F(n)=F(n-1)+F(n-2)
ret = fn2 + fn1;
// 更新中间状态
fn1 = fn2;
fn2 = ret;
}
return ret;
}
};
3. 总结
用动态规划来求解斐波那契数，那么可以达到最大的优化，时间复杂度：
O
(
n
)
O(n)
O(n)，空间复杂度：
O
(
1
)
O(1)
O(1)。
我们可以看出动态规划对于具有重叠子问题的应用具有很大的作用，不过这道题不用我们去找初始状态、边界状态、转移方程，是属于简单的题。
对于难题，如何简单的定义状态和状态如何转移是一个难点。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/80851.html
