What Is Dynamic Programming and How To Use It

Key Takeaways

hey CS dojo its YK here so in this video I'm going to talk about what dynamic programming is and how to use it and as I explain how it works I'm going to assume that you're already familiar with recursion so what is dynamic programming exactly it's actually fairly simple even though it might sound difficult it's basically a way of making your algorithm more efficient by storing some of the intermediate results and it works really well when your algorithm has a lot of repetitive computations so that you don't have to repeat those competitions over and over again and I'm gonna give you a concrete example of how it works with Fibonacci sequence so just in case you're not familiar with it phonology sequence is a sequence of numbers that starts with two ones at the beginning and each number after that is computed by adding up the two previous numbers so the third three months number is two because one plus one equals two and then the fourth 300 number is three because one plus two equals three and so on and this sequence keeps on going forever so let's say we're trying to solve the problem of finding the entrance number or writing a function called fib of n which takes a positive integer n and finds and returns the end speedruns number so if the given n is three we want to be able to find and return the third Finch number which is two and if the given n is five we want to be able to return the fifth Reynolds number which is five let's see how we can solve this problem using dynamic programming so if you want to solve a problem using dynamic programming there are typically three steps you can take the first step is to come up with a recursive solution to your problem and then in your recursive solution if you notice that there are a lot of repeated competitions you can then store some of the intermediate results so that you don't have to repeat those competitions this process is also called memoization or memorize and this is not to be confused with memorize and I've made a mistake before too and then the third step if you don't like using recursion anymore is to come up with something called a bottom-up approach so let's first see what a recursive solution might look like for this particular problem so as I said earlier we're going to write a function called fable of n which takes and a positive integer and returns the N 3 branch number and if n is equal to 1 or 2 we know that the first and the second finish numbers are 1 we're going to return 1 but instead of returning it right away we're going to store it in a temporary variable called the result and then return that instead and it's going to be clear why we need to do that later and if n is neither one nor two then we're going to return the sum of the two previous Fibonacci numbers instead fib of n minus 1 plus fib of n minus 2 store that in result and then return it at the end so the solution works but it's very very inefficient to see why let's see an example where we're trying to find the 5th Fibonacci number by calling table 5 so to find the return value of people 5 we need to first compute the return values for table 4 and people 3 so we can add them up and to find people for we need to first compute fib of 3 and peep of 2 and so on and that's what this diagram shows and looking at this diagram you might notice that there are some competitions that we repeat over and over again for example we need to compute the return value for people to three times and we need to compute the return value for fib of 3 twice here and it's not a big deal when we are trying to find the fifth or sixth minus number but if we're trying to find the hundredth free bonus number it becomes an issue and actually the time it takes to find the nth Fibonacci number grows exponentially or roughly in the order of two to the power of n and dynamic programming here says why not just store those return values for example for fib of 3 store the return value once we compute it and then use that same value when we see people 3 again in instead of computing it again and again this process is called memoization so let's see what a memorized solution looks like in code let's again consider the example where we're trying to find the fifth boomers number by calling people five the idea of this solution is going to be that we're going to use an array whose length is n plus one or six in this particular case because n here is five and then we're going to store the return value for the function of fib of n at the index n so we're going to store feeble of one which is the first few months number right here at index 1 and then fib of 2 at index 2 and so on and initially we're going to set all these values to now and we're going to write our function of fib and this is going to take two arguments instead of just one the first one is the same as before and a positive integer and the second one is going to be this array and so you need to initialize the survey memo before you call this function now at the beginning of this function check if memo at index n is null or not if it's not equal to now that'll mean that we've already seen this argument N and we've already stored the return value for that at the index n a memo so just return that instead so we turn memo square brackets and otherwise the following part is the same as before if n is equal to 1 or 2 we turn one store 1 in result and then return that at the end and if that's not the case then find the sum of the two previous fabulous numbers and then return that instead and then what's new in this function is that before you return this result the return value you need to store it in memo at index n so that you can use it later now let's now think about the time complexity for the solution we're going to call it T of n this is going to be the time it takes to find the nth Fibonacci number with this particular method and we're going to find that by multiplying the number of times we call this function baby with the time it takes to execute each of those calls we're going to call that T now there are only two ways we're going to call this function of fib the first way is when we call this function for the first time with the arguments and and memo to find the NSP ones number and the second way is from this line right here and notice that if you look at this whole block after this first if clause this whole block is only executed most n times and this is true because there are n possible arguments to this function that's 1 through N and each time this function is called with each of those arguments the return value will be stored a memo at index n so after the first time this function is called with each argument we'll never get to this block and each time this block is executed fib is called a most twice if we get to this line so the number of times fib is called is at most two times n plus 1 so 2 n it comes from this block right here and one comes from the first time we call this function fib and the time it takes to execute each of those calls this T right here is going to be a constant time or a Big O of 1 and this is because if you look at each operation in this function excluding these recursive calls that follow each operation is a constant time operation and when you have a constant time operation when you add them up you still get a constant time operation which is big-oh of one and that's why we have Big O of one here and so T of N or the time it takes to find the nth feminist number with this particular method is going to be 2 n plus 1 times Big O of 1 which is Big O of 2 n plus 1 which is equal to Big O of N and this is a huge improvement from what we had earlier which was Big O of 2 to the power of n now let's now examine how this memo array is actually filled so let's say we're trying to find the 5th Fibonacci number again and when we call fib with the argument 5 and memo of course we'll see that we don't have a stored value at the index 5 yet so we go down and we're going to ask ourselves what's the value of fib of 4 and then 3 and so on and when we get to fever of 2 we'll know that this value is 1 so we're gonna store it at index 2 right here and same with people 1 that's 1 right here and once we have these two values we'll be able to find the third a Fibonacci number which is fib of 3 right here and then once we find the value by adding them up store that value right here so we can use it later and then when we go up to feeble 4 we'll add 1 and 2 right here and we get 3 and so on until we get here and so as you can see this array is mostly filled from left to right so when you see this you might say why not just explicitly build this array from left to right from scratch instead of building a recursively and that's the idea behind a bottom-up approach so let's see what a bottom-up approach might look like in code we're going to define a function called fab bottom-up which takes an a positive integer just like before and returns the nth Fibonacci number and then if n is equal to 1 or 2 of course we're going to return 1 and after that we're going to define an array whose lie is going to be n plus 1 where n plus 1 is 6 of course if we're trying to find the fifth Fibonacci number right here if n is equal to five and after that we're going to set the first and the second elements of this array bottom up to be 1 these two items right here and then we're going to run a for loop for I from 3 which corresponds to this item right here up to N and n corresponds to the last item right here of this array and whatever index we're examining currently we're going to set that element at the index I or bottom up square brackets I to be the sum of the two previous items so in this particular example we'll have two here three here and after that we're going to return the last item in bottom up or bottom up square brackets N and we're done the time complexity for this algorithm will be again Big O of n because we're going to define this array and go through this array only once ok so that's how dynamic programming works but now I'm going to show you a quick demo with Python and something called Jupiter notebook to show you how this idea of my play out in practice so in this jupiter notebook i have defined a few functions in Python fib of n which is a recursive naive recursive solution and river of memo and people to which represent a memorized solution and fifth bottom up which is of course a bottom up solution so let's see how they compare to each other in performance we're gonna try running fib of n first the naive recursive solution with fever five and that gives us 5 which is expected what about fever of 20 that gives us the answer pretty quickly - and what about fever of 35 this actually takes five to six seconds on my computer so it's obviously not the most efficient approach let's see how fib of 2 and 3 both memo the memorized solution compares to that let's try running fifth memo of 5 first and that gives us five which is expected and what about 50 mm or 35 that's pretty quick - and what about 50 ml 100 and 1000 this actually gives us an error and this error is called a recursion error Python gives us this er actually because there are too many recursive calls on a call stack and to fix that we can just use the bottom-up approach one advantage of using a bottom-up approach is that we don't have to put any recursive calls on a call stack so we don't have to worry about that so we're going to load this function and then run it with the argument 35 which is pretty quick 1000 and then let's try 10,000 as well and that's pretty instantaneous - okay so that's my introduction to dynamic programming let me know in the comment section below what you thought of this video and if you have any requests about what kind of videos I should make in the future let me know in the comment section below as well I'm YK from CES dojo and I'll see you in the next video