题目描述
blablabla
样例
blablabla
算法1
(递推) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int Fibonacci(int n) {
int Fib[n + 1] = {0} ;
Fib[1] = Fib[2] = 1 ;
for (int i = 3; i <= n; i++)
Fib[i] = Fib[i - 1] + Fib[i - 2] ;
return Fib[n] ;
}
};
算法2
(滚动数组) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int Fibonacci(int n) {
if (n == 0)
return 0 ;
else if (n <= 2)
return 1 ;
int lst1 , lst2 , res = 0 ;
lst1 = lst2 = 1 ;
for (int i = 3; i <= n; i++)
res = lst1 + lst2 , lst1 = lst2 , lst2 = res ;
return res ;
}
};
算法3
(递归) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int Fibonacci(int n) {
if (! n)
return 0 ;
if (n == 1 || n == 2)
return 1 ;
return Fibonacci (n - 1) + Fibonacci (n - 2);
}
};
算法4
(记忆化ss) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int a[50] ;
int Fibonacci(int n) {
if (! n)
return 0 ;
if (a[n] != 0) {
return a[n];
}
if (n == 1 || n == 2) {
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
};
算法5
(打表) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int Fibonacci(int n) {
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 1;
if(n==3) return 2;
if(n==4) return 3;
if(n==5) return 5;
if(n==6) return 8;
if(n==7) return 13;
if(n==8) return 21;
if(n==9) return 34;
if(n==10) return 55;
if(n==11) return 89;
if(n==12) return 144;
if(n==13) return 233;
if(n==14) return 377;
if(n==15) return 610;
if(n==16) return 987;
if(n==17) return 1597;
if(n==18) return 2584;
if(n==19) return 4184;
if(n==20) return 6765;
if(n==21) return 10946;
if(n==22) return 17711;
if(n==23) return 28657;
if(n==24) return 46368;
if(n==25) return 75025;
if(n==26) return 121393;
if(n==27) return 196418;
if(n==28) return 317811;
if(n==29) return 514229;
if(n==30) return 832040;
if(n==31) return 1346269;
if(n==32) return 2178309;
if(n==33) return 3524578;
if(n==34) return 5702887;
if(n==35) return 9227456;
if(n==36) return 14930352;
if(n==37) return 24157817;
if(n==38) return 39088169;
if(n==39) return 63245986;
}
};
算法6
(矩阵快速幂) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
struct matrix {
int a[105][105];
};
const int N = 2;
matrix mul(matrix A, matrix B, bool flag = false) {
matrix res;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
res.a[i][j] = 0;
for (int k = 1; k <= N - flag; ++k) {
res.a[i][j] += A.a[i][k] * B.a[k][j];
}
}
}
return res;
}
matrix unit() {
matrix res;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
if (i == j) {
res.a[i][j] = 1;
} else {
res.a[i][j] = 0;
}
}
}
return res;
}
matrix pow(matrix A, int n) {
matrix res = unit();
while (n) {
if (n & 1) {
res = mul(res, A);
}
A = mul(A, A);
n >>= 1;
}
return res;
}
int Fibonacci(int n) {
if (! n)
return 0;
matrix A;
A.a[1][1] = A.a[1][2] = A.a[2][1] = 1;
A.a[2][2] = 0;
A = pow(A, n - 1);
matrix res;
res.a[1][1] = res.a[2][1] = 1;
res = mul(res, A, true);
return res.a[2][1];
}
};
算法7
(通项公式) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int Fibonacci(int n) {
double t = sqrt (5) ;
long long r = (pow ((1 + t) / 2 , n) - pow ((1 - t) / 2 , n)) / t ;
return r ;
}
};
rq完结
orz