Intro to Dynamic Programming

In my job hunt, I’ve been doing a deeper dive into things like data structures and other important concepts that sometimes come up during interviews. One concept that I didn’t know much about, and am beginning to learn more, is Dynamic Programming. This week I wanted to share a little bit of the knowledge I’ve gained on the subject.

What is Dynamic Programming?

Let’s look at the math problem below:

1+1+1+1+1+1+1+1+1+1+1+1 = ?

After a few seconds of counting, we can see that the answer is 12. Now, after we figured that out, what if we add another +1 to the end of that equation? We would come up with the answer exponentially quicker. That is because we are simply adding 1 to 12 instead of scanning the computer screen and counting the number of 1s there and then adding it up. This is, in essence, dynamic programming. Instead of doing the same step, over and over again, when we know the answer, we store the information and make it simpler to come up with new solutions after new information is given.

A Coded Example

One fairly easy and common example of dynamic programming can be shown using Fibonacci’s Sequence. For those who don’t know, the Fibonacci Sequence is a series of numbers where the next number is calculated by adding up the previous two, [0, 1, 1, 2, 3, 5, 8, 13, 21, 34…] and so on and so forth. Now, let’s say we’re tasked with writing a function that, when given a number, gives us the value in Fibonacci’s Sequence at that number’s location in the array. This isn’t too difficult, and we can do this recursively with something like this:

function fib(n) {  
   if (n < 2) return n;  
 
   return fib(n - 1) + fib(n - 2);
}

This will give us our desired output. If we give it 7, for example, it will return 13. Nice and clean, solved in only two lines of code. However, this is also EXTREMELY slow. We’re talking Big-O of O(2^n) slow, which is nowhere near good enough. This is because as n increases, the recursion branches off exponentially in order to find the solution. Now, let’s look at a solution that uses some dynamic programming.

function fib(n){ 
  let dp = [0,1];   
  for(let i = 2; i < n; i++){
    let result = dp[0] + dp[1]
         dp[0] = dp[1]
         dp[1] = result;
   }
  return dp[1]
}

Here, we create an array with the first few elements of Fibonacci's Sequence. Then, we set up a for loop and a temporary value in the form of result. We get result by adding up the two previous values, and then shuffle and reassign the values of dp[0] and dp[1], ending with dp[1] — the last value of our array and our solution. Not as tidy, but still very clean and easy, and more importantly, efficient.

This is a basic introduction to the concept of Dynamic Programming. I hope this was helpful!