Dynamic Programming in Javascript
What is dynamic programming ?
A method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. Dynamic programming works on problems with Optimal substructure and Overlapping subproblems.
Optimal substructure
A problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. Example:

Looking at the diagram above, to determine the shortest path from A to D, we can first determine the shortest path from A to B and then A to C and use the optimal solutions to determine the shortest path from A to D.
Overlapping subproblems
A problem is said to have overlapping subproblems if it can be broken down into subproblems which are reused several times. Example: Fibonacci sequence- Every number after the first two is the sum of the two preceding ones

From the diagram above, to get Fibonacci of 7— we need to calculate Fibonacci of 5 twice, Fibonacci of 4 thrice and Fibonacci of 3 multiple times. The performance implication of this is when the input size grows, the amount of time it takes to provide a solution increases because some operations are performed multiple times.
This is where dynamic programming comes into play! Once it has performed the operation once, it is stored in an array so when that operation is found again, the solution just get picked up from the array. This will be demonstrated by implementing Fibonacci sequence in Javascript!
We can use dynamic programming in two forms -
- Memoization — Top Down
- Tabulation — Bottom Up
We’re going to explore both implementation as well as their time complexity. Let’s dive in.
F(n) = F(n-1) + F(n-2)Above is the formula to calculate the fibonacci of a particular number say F(5) will be F(4)- F(3).
Let’s explore a recursive solution .
const fib = (n) => {
if(n<= 2) return 1;
return fib(n-1)+ fib(n-2)}
Yup! we just implemented Fibonacci with few lines of code. But guess what ? the time complexity is exponential (O(2^N)). I ran this code in my browser in the source tab , using fib(100) — do not try this. I had my browser frozen! Why did this happen ? Because It calculates the fibonacci of most numbers multiple times. In situations like this, we use dynamic programming where we can just store the values of previously calculated fibonacci.
Memoization — The Top down approach
Storing results of expensive function calls and returning the cached result when the same inputs occur again.
const fib=(n, memo=[])=>{
if(memo[n] !== undefined) return memo[n]
if(n <= 2) return 1;
let res = fib(n-1, memo) + fib(n-2, memo);
memo[n] = res;
return res;
}The time complexity for this is 0(N) which is much better than the exponential time complexity of the initial solution.
Tabulation- The Bottom up approach
Storing the result of a previous result in a “table” (usually an array). Better space complexity can be achieved using tabulation
const fib=(n)=>{
if(n <= 2) return 1;
let fibArray = [0,1,1];for(let i = 3; i <= n; i++){
fibArray[i] = fibArray[i-1] + fibArray[i-2];
}
return fibArray[n];
}
Dynamic programming is used in
- Artificial Intelligence
- Caching
- Shortest Path Algorithms etc
Thanks for reading😌❤
