算法1
(递归算法) $O(n^2)$
当n==1时,f(n)=0;
当n<=2时,f(n)=1;
当n>3时,f(n)=f(n-1)+f(n-2).
java 代码
public int fun(int n ) {
if (n == 0 ) return 0;
if (n <= 2 ) return 1;
return fun(n-1)+fun(n-2);
}
算法2
(递推算法) $O(n)$
斐波那契数列形式如下:
F ( n ) = {
1 n = 1
1 n = 2
F ( n − 1 ) + F ( n − 2 ) n >= 3
}
斐波那契数列的前缀和公式为s ( n ) = f ( n + 2 ) − 1
java 代码
class Solution {
public int Fibonacci(int n) {
if (n == 0 ) return 0;
if(n <= 2) return 1;
int a = 1 , b = 1, c = 0;
for(int i = 3; i <= n; i ++){
c = a+b;
a = b; //将b保存到a中
b = c; //将c保存到b中
}
return c;
}
}