CareerCup

it depends how what kind of optimization you want.
If optimization of speed, use caching.
If optimization of memory, just try this:

int first = 0;
int second = 1;
for (int i = 3;i <= n;i ++){
 second = first + second;
 first = second - first;
}
cout << second << endl;
}

- Anonymous February 04, 2010 | Flag Reply

write two functions...than it wud be possible assuming series is: 0 1 1 2 3 5 8....... {{{ fib(int n) { return n==1?0:fib2(n,0,1) } fib2(int n,int a, int b) { return n==1?a:fib2(n-1,b,a+b); } wud work 1: 1 0 1---->0 2: 2 0 1 1 1 1---->1 3: 3 0 1 2 1 1 1 1 2--->1 4: 4 0 1 3 1 1 2 1 2 1 2 3---->2 5: 5 0 1 4 1 1 3 1 2 2 2 3 1 3 5--->3 and so on - utscool@gmail February 15, 2010 | Flag Reply

write two functions...than it wud be possible assuming series is: 0 1 1 2 3 5 8....... {{{ fib(int n) { return n==1?0:fib2(n,0,1) } fib2(int n,int a, int b) { return n==1?a:fib2(n-1,b,a+b); } wud work 1: 1 0 1---->0 2: 2 0 1 1 1 1---->1 3: 3 0 1 2 1 1 1 1 2--->1 4: 4 0 1 3 1 1 2 1 2 1 2 3---->2 5: 5 0 1 4 1 1 3 1 2 2 2 3 1 3 5--->3 and so on - utscool@gmail February 15, 2010 | Flag Reply

f=0 s=1
print "f"
print "s"
while (counter>0)
{
f=s+f
s=f-s
print "f"
}

- clrs March 03, 2010 | Flag Reply

check this link, it has a log n approach:

ics.uci.edu/~eppstein/161/960109.html

- fragzilla March 13, 2010 | Flag Reply

A non recursive solution saving current & previous OR us an array to save fib. no. calculated so far. Both solutions are example of dynamic programming but second uses O(n) time

- M August 08, 2010 | Flag Reply