# Exercise 15.1.5

The Fibonacci numbers are defined by recurrence (3.22). Give a $\O(n)$-time dynamic-programming algorithm to compute the $n$th Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?

We don't really need a dynamic programming approach, do we? Anyway, let's implement one.

The subproblem graph is pretty trivial to draw, and I was going to skip the whole dot exercise, but then I drew it on paper, and there is a pretty interesting property. Specifically, the non-optimal version for solving $n$ has $F_n$ vertices, where $F_i$ is the $i$-th Fibonacci number.

The other is pretty straightforward, although graphviz doesn't render it perfectly.

### Python code

def fibonacci(n): results = [0] * (n + 1) results[1] = 1 for i in range(2, n + 1): results[i] = results[i - 1] + results[i - 2] return results[n]