-
Notifications
You must be signed in to change notification settings - Fork 3
Dynamic Programming
There are two main approaches for dynamic programming: top down and bottom up.
The Fibonacci sequence is the easiest way to contrast these two methods.
A typical Fibonacci recursive implementation:
int fibonacci(n) {
if(n < 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}The list below shows the subsequent recursive calls for fibonacci(5).
fibonacci(5) -> fibonacci(4) + fibonacci(3)
fibonacci(4) -> fibonacci(3) + fibonacci(2)
-> fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0)
-> fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0)
fibonacci(3) -> fibonacci(2) + fibonacci(1)
-> fibonacci(1) + fibonacci(0) + fibonacci(1)
Even with for small n, it's apparent that there are multiple duplicate calculations. For example, fibonacci(3) is called twice, and fibonacci(2) 3 times. This is amplified exponentially when dealing with larger n values.
int fibonacci(n) {
Map<Integer, Integer> nToFibonacciMap = new HashMap<>();
nToFibonacciMap.put(0, 1);
nToFibonacciMap.put(1, 1);
// Start at bottom and populate map for higher values.
for(int i = 3; i <= n; i++) {
int currentFibonacciValue = nToFibonacciMap(i - 1) + nToFibonacciMap(i - 2);
nToFibonacciMap.put(i, currentFibonacciValue);
}
return nToFibonacciMap(n);
}The bottom up approach starts with calculating and caching base values. These base values are then used to build towards the desired result.
With the Fibonacci sequence, the trivial cases where n < 2 can be assigned and then used to calculate fibonacci(2). After caching the result for fibonacci(2), fibonacci(3) can be calculated using the cached values for fibonacci(1) and fibonacci(2), eliminating any duplicate calculations.