斐波那契（Fibonacci）数列的应用非常多。
【递推公式】
f(n) = n （n=0 或 n=1）
f(n) = f(n-1) + f(n-2) （n≥2）
【参考程序】
// 递归，时间复杂度 O(2^n)
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
// 递推
int fibonacci(int n) {
if (n <= 1) return n;
int f0 = 0, f1 = 1, f = 0;
for (int i = 2; i <= n; i++) {
f = f0 + f1;
f0 = f1;
f1 = f;
}
return f;
}
// 空间换时间，生成斐波那契数列前 n 项（动态规划）
vector<int> generateFibonacci(int n) {
vector<int> fib(n, 0);
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i < n; ++i) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib;
}