-
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 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.
public class Fibonacci {
Map<Integer, Integer> nToFibonacciMap = new HashMap<>();
int topDownFibonacci(n){
Integer result = nToFibonacciMap.get(n);
if(n < 2) {
result = 1;
}
else {
if(result == null) {
// The first Fibonacci call will populate the cache
// while the second call uses the values from the cache.
result = topDownFibonacci(n - 1) + topDownFibonacci(n - 2);
nToFibonacciMap.put(n, result);
}
}
return result;
}
}The top down or memoized approach consists of the following steps:
- Break the initial problem up into subproblems.
- Perform a cache lookup for answers to the subproblems.
- When a cache miss occurs, calculate the subproblem solution and cache it so subsequent calls can re-use the answer without duplicating the work needed to get it.
int bottomUpFibonacci(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.
Problem
Given an array of coin values [1, 5, 10, 25] and a sum S, find the combination of coins that sum to S that uses the minimum amount of coins.
int[] makeChange(int[] coinValueList, int sum) {
List<Integer>[] memoizedSolutionArray = new List<>[];
// Start populating sums starting from 0.
for(int i = 0; i <= sum; i++) {
memoizedSolutionArray[i] = new ArrayList<>();
// Consider all coin values
for(int j = 0; j < coinValueList.length; j++) {
int coinValue = coinValueList[j];
if(coinValue <= i) {
List<Integer> memoizedSolution = memoizedSolutionArray[i];
if(memoizedSolution.size() == 0) {
memoizedSolution.add(coinValue);
}
else {
List<Integer> memoizedRemainder = memoizedSolutionArray[i - coinValue];
if(memoizedRemainder.size() + 1 < memoizedSolution.size()) {
List<Integer> newSolution = new ArrayList<>(memoizedRemainder);
newSolution.add(coinValue);
memoizedSolutionArray[i] = newSolution;
}
}
}
}
}
return memoizedSolutionArray[sum];
}