509. 斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
方法1 递归
思路
根据题目给出的定义可以看出斐波那契数列是递归定义的，因此很容易就可以写出递归的代码如下：
代码
class Solution {
public int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
}
复杂度分析
-
时间复杂度$O(2^N)$
Master公式
-
空间复杂度$O(N)$
递归调用栈空间
方法2 记忆化递归
思路
把每个$F(n)$保存起来，如果计算过就不计算了，空间换时间
代码
class Solution {
private int[] help;
public int fib(int n) {
if (n < 2) return n;
help = new int[n + 1];
help[0] = 0;
help[1] = 1;
return process(n);
}
private int process(int n) {
if (n < 2) return n;
return help[n] = helpCompute(n - 1) + helpCompute(n - 2);
}
private int helpCompute(int n) {
int res = 0;
if (help[n] != 0) {
res = help[n];
} else {
res = process(n);
}
return res;
}
}
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
方法3 动态规划
思路
从前往后递推
代码
class Solution {
public int fib(int n) {
if (n < 2) return n;
int[] help = new int[n + 1];
help[0] = 0;
help[1] = 1;
for (int i = 2; i < help.length; i++) {
help[i] = help[i - 1] + help[i - 2];
}
return help[n];
}
}
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
方法4 动态规划空间优化
思路
代码
class Solution {
public int fib(int n) {
if (n < 2) return n;
int first = 0;
int second = 1;
int res = 0;
for (int i = 2; i <= n; i++) {
res = first + second;
first = second;
second = res;
}
return res;
}
}
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
方法5 通项公式
思路
- a[n+2]=a[n+1]+a[n]
- 设常数k，k满足：
- a[n+2]+k*a[n+1]=k*a[n+1]+a[n+1]+a[n]
- a[n+2]+k*a[n+1]=(k+1)*{a[n+1]+a[n]*1/(k+1)}
- 计算k=1/(k+1)，得解k1与k2
- 于是分别有： a[n+2]+k1*a[n+1]=(k1+1)(a[n+1]+k1*a[n])及 a[n+2]+k2*a[n+1]=(k2+1)(a[n+1]+k2*a[n])
- 易知a[n+1]+k1*a[n]及a[n+1]+k2*a[n]分别为等比数列，解得该两项数列的通项公式
- 两数列相消即可求得a[n]的通项公式
代码
class Solution {
public int fib(int n) {
double sqrt5 = Math.sqrt(5);
double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
return (int) Math.round(fibN / sqrt5);
}
}
复杂度分析
方法6 矩阵快速幂
思路
代码
class Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
//int[][] q = 1, 1
// 1, 0
int[][] res = pow(q, n - 1);
return res[0][0];
}
public int[][] pow(int[][] a, int n) {
//int[][] ret =
//1, 0
//0, 1
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
}
快速幂算法能帮我们算出指数非常大的幂，传统的求幂算法之所以时间复杂度非常高（为O(指数n)），就是因为当指数n非常大的时候，需要执行的循环操作次数也非常大。所以我们快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。让我们先来看一个简单的例子：
3^10=3*3*3*3*3*3*3*3*3*3
//尽量想办法把指数变小来，这里的指数为10
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
3^10=(3*3)^5
3^10=9^5
//此时指数由10缩减一半变成了5，而底数变成了原来的平方，求3^10原本需要执行10次循环操作，求9^5却只需要执行5次循环操作，但是3^10却等于9^5,我们用一次（底数做平方操作）的操作减少了原本一半的循环量，特别是在幂特别大的时候效果非常好，例如2^10000=4^5000,底数只是做了一个小小的平方操作，而指数就从10000变成了5000，减少了5000次的循环操作。
//现在我们的问题是如何把指数5变成原来的一半，5是一个奇数，5的一半是2.5，但是我们知道，指数不能为小数，因此我们不能这么简单粗暴的直接执行5/2，然而，这里还有另一种方法能表示9^5
9^5=（9^4）*（9^1）
//此时我们抽出了一个底数的一次方，这里即为9^1，这个9^1我们先单独移出来,剩下的9^4又能够在执行“缩指数”操作了，把指数缩小一半，底数执行平方操作
9^5=（81^2）*(9^1)
//把指数缩小一半，底数执行平方操作
9^5=（6561^1）*(9^1)
//此时，我们发现指数又变成了一个奇数1，按照上面对指数为奇数的操作方法，应该抽出了一个底数的一次方，这里即为6561^1，这个6561^1我们先单独移出来，但是此时指数却变成了0，也就意味着我们无法再进行“缩指数”操作了。
9^5=（6561^0）*(9^1)*(6561^1)=1*(9^1)*(6561^1)=(9^1)*(6561^1)=9*6561=59049
我们能够发现，最后的结果是9*6561，而9是怎么产生的？是不是当指数为奇数5时，此时底数为9。那6561又是怎么产生的呢？是不是当指数为奇数1时，此时的底数为6561。所以我们能发现一个规律：最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。
上述方法的代码如下
long long fastPower(long long base, long long power) {
long long result = 1;
while (power > 0) {
if (power & 1) {//指数为奇数
result = result * base % 1000;//此时记得要把指数为奇数时分离出来的底数的一次方收集好
}
power >>= 1;
base = (base * base) % 1000;//底数变大成原来的平方
}
return result;
}
矩阵快速幂可以把每个矩阵看成一个数，代入上面的普通的快速幂代码中，result=1，对应单位矩阵。
复杂度分析
- 时间复杂度：$O(logN)$
- 空间复杂度：$O(1)$
方法7 查表
static final int[] fibs = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040};
public int fib(int N) { return fibs[N]; }
复杂度分析
- 时间复杂度：$O(1)$
- 空间复杂度：取决于数组中存储的结果的个数
参考
- https://leetcode-cn.com/problems/fibonacci-number/solution/6chong-jie-fa-jie-jue-fei-bo-na-qi-shu-lie-by-sunh/
- https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/
- https://blog.csdn.net/qq_19782019/article/details/85621386
- https://blog.csdn.net/qq_42817826/article/details/81565569
- https://www.zhihu.com/question/264953934
