前置知识
斐波那契数列是一种经典的数学序列，它以递归的方式定义。斐波那契数列的前两个数是 0 和 1，之后的每个数都是前两个数之和。换句话说，数列中的每个数（从第三个数开始）都是前两个数之和。
斐波那契数列的数学表达式如下：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (对于n ≥ 2)根据上述定义，斐波那契数列的前几个数依次为：0, 1, 1, 2, 3, 5, 8, 13, 21, ...
下面介绍几种不同的计算斐波那契数列的方法：
- 递归方法：最直观的计算斐波那契数列的方法是使用递归。具体实现代码如下：
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}这种方法简单易懂，但在计算较大的斐波那契数时会导致性能问题，因为它会重复计算相同的子问题。
- 迭代方法：为了避免重复计算，我们可以使用迭代的方式计算斐波那契数列。具体实现代码如下：
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int fib = 1;
int prevFib = 1;
for (int i = 2; i < n; i++) {
int temp = fib;
fib += prevFib;
prevFib = temp;
}
return fib;
}迭代方法通过从前往后计算每个斐波那契数，只需保存前两个数即可，避免了重复计算。
- 数组缓存方法：为了进一步提高效率，我们可以使用一个数组来缓存已经计算过的斐波那契数，从而避免重复计算。具体实现代码如下：
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int[] fibs = new int[n + 1];
fibs[0] = 0;
fibs[1] = 1;
for (int i = 2; i <= n; i++) {
fibs[i] = fibs[i - 1] + fibs[i - 2];
}
return fibs[n];
}这种方法在计算较大的斐波那契数时效率更高，因为已经计算过的数不需要重复计算。
以上是几种常见的计算斐波那契数列的方法，它们各有优劣。对于较小的斐波那契数，递归方法可以直观地实现；对于较大的斐波那契数，建议使用迭代或数组缓存方法以提高效率。
例题
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。
示例 1：
- 输入：2
- 输出：1
- 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
- 输入：3
- 输出：2
- 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
- 输入：4
- 输出：3
- 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
- 0 <= n <= 30
采用动态规划
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55
示例代码
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
vector<int> dp(N + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
};