Dynamic Programming: Intro
One of the first things you’ll learn about programming is the idea of recursive functions. In short, your function will call upon itself until it reaches an end case. A great example of this is the Fibonacci Sequence.
In short, the idea of the fibonacci sequence is to add the previous two elements for a new element. This can go on infinitely and most cases you’ll want to know the number in a specific position. Most people use a recursive function and although it’s a great start, it’s incredibly slow.
Although this works, if you look at my breakdown you’ll notice that you’re calculating the same things over and over again. There’s no reason to calculate all the way down to ‘fib(1)’ n amount of times when you’ve already done it once.
Dynamic Programming gets rid of this headache of a process and it becomes a faster and more efficient way of doing the same thing. For this example we’ll make use of memoization which kind of sounds like memorization and that’s how I think about it. So let’s break it down. When dealing with fibonacci sequence, we start with our first two numbers 0 and 1. The third number is the sum of that which is 1 and now we have fib = 0,1,1. Great, so if we keeping going our fourth element will be the sum of 1 and 1 and now fib = 0,1,1,2. Notice that we don’t care about 0 after it’s been used. Likewise we won’t need 1 at index 1 when summing 2 and 1. You’ll notice a pattern that at any given moment, you really just care about two digits.
So let’s break this down. We know that fibonacci’s sequence start from 0 and 1 and from there on out, it’s the sum of the last two element of the array. We initialize our array and from there we update those two items with the integers of our interest. Starting at 0 and 1, we sum the two and update the array to be [1,1]. This works great because we don’t really care about that 0 anymore. It’s been calculated and we don’t need it anymore. Let’s keep moving. We sum up 1 and 1 and get 2. Great, now we update our array to be [1,2]. The last element at i = 1 will always be the sum of the previous two, and the elements in the entire array will give us the value of our next integer if we need it. Lastly, our for loop only runs as long as the position we’re interested in so that we we only calculate up to that point. So starting with index 0 and 1, our for loop iterates n-2 times since we already have the first two.
You’ll know you can make use of dynamic programming when you need to access something you’ve previously done such as in the case of fibonacci’s sequence. Think about it as if you were in a park reading a book, and someone asks you for the name of the book. At first, you’ll look at the front cover and respond. Then n amount of people ask you about the
