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(2n) 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.