long fibonacci(int n){
assert(n>=0);
if(n == 0) return 1;
if(n == 1) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
long fibonacci(int n){
if(n ==0 ) return 1;
long[] fibs = new long[n+1];
fibs[0] = 1;
fibs[0] = 2;
for(int i=2;i<=n;i++){
fibs[i] = fibs[i-1] + fibs[i-2];
}
return fibs[n];
}
long fibonacci(int n){
if(n==0) || (n==1) return 1;
int sum = 0;
int number0 = 1;
int number1 = 1;
for(int i=2;i<=n;i++){
sum = number0 + number1;
number0 = number1;
number1 = sum;
}
return sum;
}