#### Example of Dynamic Programming: Fibonacci numbers

The Fibonacci numbers are defined by the following recurrence:

F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2) for N > 1.

Give a recursive algorithm to compute this.

int f(int n) {
if (n <= 1) return n;
return f(n-1) + f(n-2);
}

The running time of this algorithm is at least 2^{n/2}.
(Prove this using a recursion diagram.)

If instead we using caching or bottom-up dynamic programming,
we reduce the running time to O(n).

Caching:

int f(int n) {
static HashTable<int,int> cache;
if (n <= 1) return n;

if (! cache.exists(n)) cache[n] = f(n-1) + f(n-2);

return cache[n];
}

Now what is the recursion diagram?

Bottom up dynamic programming.
Since we know the structure of the recursion diagram in advance,
we can simply iterate to compute all the sub-problems' solutions
"bottom up":

int f(int n) {
Array <int> cache(0);

cache[1] = 1;

for (int i = 2; i <= n; ++i)
cache[i] = cache[i-1] + cache[i-2];

return cache[n];
}

THis of course takes time O(n).

### References