0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,144,233,377,610,987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, ...
The numbers keep getting bigger, time keeps passing, and I get closer to death. I need a faster way to find the nth fibonacci number, or I will starve to death. I will use dynamic programming to find the nth fibonacci number in O(n) time.
public class fibonacci {
static int fib(int n)
{
int f[] = new int[n + 2];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
I have now found the nth fibonacci number in O(n) time. This represents the fact that if we put our minds to it, we can overcome any obstacle in our way. However, this dynamic programming uses O(n) space, and could be improved to O(1) space. This represents the fact that there is no such thing as perfection, and honing our skills is a lifelong process. However, since I found a polynomial time solution to this problem, I won't starve to death before finding the 10000th fibonacci sequence. This is good, because it represents the fact that African children won't go hungry anymore.
I did it. I found the nth fibonacci number in O(n) time.