This article is my own summary about Dynamic Programming algorithm. The first time I heard bout this term is from What is Dynamic Programming and Hot wo use it by YK Sugishita. He started with Fibonacci squence. We all know to resolve it by using recursion.
const fibRecursive = function(n){
if (n <= 2) return 1;
return (fibRecursive(n-1) + fibRecursive(n-2));
}
It looks pretty straight forward, the drawbacks are using a lot of computing power, and memory space.
We can interate the above recursive code to the following notation:
We can see that, F1 and F0 are the base cases of the recursive. And by looking at calaculation further down, the current value would be the sum of the previouse 2 values.
From the notation above, we can see F(3), F(2) have be recalcuated serval times. Our example is a small number, but if we try to calculate to a bigger number, it will be ended up to O(2^n). Since there are repeated calculation occurred, we can store all the numbers that are calculated, and reused them when they are needed.
What is Dynamic Programming (DP)?
Dyanmic Programming is an algorithmic technique is to break a large problem down into incremental steps sot that, at any given stage, optimal solutions are known to sub-problems.
So from the above picture, we can solve the Fibonacci sequence to break down into F(0) and F(1), and from this to get the F(n) we need to calculate.
Dynamic Programming methods
There are two methods can be used to solve the problems:
- Top-dwon with Memoization
const fibMemoz = function(n){
let arr = new Array(n + 1).fill(null);
function fibMemozHelper(n){
if (arr[n] !== null) {
return arr[n];
} else {
if(n <= 2) {
arr[n] = 1;
return 1;
} else {
let result = fibMemozHelper(n-1) + fibMemozHelper(n-2);
arr[n] = result;
return result;
}
}
}
let result = fibMemozHelper(n);
return result;
}
- Bottom-up with Tabluation
const fibButtomUp = function(n){
let arr = new Array(n+1).fill(null);
arr[1] = 1;
arr[2] = 1;
for (let i = 3; i <=n; i++){
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n];
}