方案一：
public class Solution {
public int Fibonacci(int n) {
if(n==0)
return 0;
if(n<3)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
方案二：
public class Solution {
public int Fibonacci(int n) {
if(n==0)
return 0;
if(n<3)
return 1;
int f1=1;
int f2=1;
int result=0;
for(int i=3;i<=n;i++){
result=f1+f2;;
f1=f2;
f2=result;
}
return result;
}
}
时间和内存对比方案 时间 内存方案一 772 4416方案二 21 9104
建议：尽量用方案二，方案二一般更省内存，但方案一的思想更简单，代码量更少