# Dynamic Programming

Dynamic Programming is an optimization to the recursion method. The concept stores the results of subproblems to avoid recomputation and reduces the time complexity from exponential O(2^{n}) to linear O(n).

Here is Fibonacci on recursion.

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

Here is the method above is optimized using memoization.

```
int fibonacci_memorize(int n) {
if (numbers[n]) return numbers[n];
if (n <= 2) {
numbers[n] = 1;
} else {
numbers[n] = fibonacci_memorize(n - 1) + fibonacci_memorize(n - 2);
}
return numbers[n];
}
```

Here is the bottom-up approach. No recursive function. The best.

```
int fibonacci_iterative(int n) {
if (n <= 1) return n;
int result = 1;
int less_one = 0;
int less_two;
for (int i = 2; i <= n; i++) {
less_two = result;
result += less_one;
less_one = less_two;
}
return result;
}
```

You could see my article about iteration and recursion here. That is why I prefer the iteration method. Linear time is the best.