Dynamic Programming in Javascript

Sogunle Omowunmi
Nov 6 · 3 min read

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😌❤

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade