Dynamic Programming Explained (Practical Examples)

Key Takeaways

[Music] in this video i'll be explaining to you dynamic programming specifically i'll go through the definition and the theory then i'll talk about how you classify different problems and understand if you can use dynamic programming for them then i'll get into a few examples where i explain how to implement dynamic programming as well as how you can optimize otherwise poor time complexity solutions using dynamic programming now i do want to mention that i do have a programming course it's called programming expert you can check it out from the link in the description it teaches fundamental and advanced programming concepts mostly in python but soon in some other languages as well as well as software engineering tools software design has over 100 videos hundreds of practice questions multiple programming projects if you guys want to check it out and support me please do from the link in the description you can use discount code tim i think it's a great resource to get better at programming regardless with that said let's get into dynamic programming so let me start here by reading the definition dynamic programming is an algorithmic technique for solving an optimization problem by breaking it down into simpler sub problems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its sub problems so this is a very general definition and this describes a variety of ways of solving problems but the key here is that we are breaking a problem down into simpler sub problems and then solving those sub problems and the solutions of those sub problems are going to lead us to the solution of the overall problem now this can be tricky because sometimes you can have problems that can be broken into sub problems however the solutions of those sub problems do not necessarily lead you towards the optimal solution of the overall problem so optimization problems really involve finding the best answer out of multiple answers and you'll so you'll see dynamic programming is used many times when you're trying to maximize a value or minimize a value or again find the best answer out of a variety of different answers based on whatever criteria that may mean now you can use dynamic programming for problems that are not optimization problems or not by definition optimization problems i'm actually going to show you an example of that right now so to better illustrate this because i understand it's still probably confusing i'm just going to go through the famous example which is the fibonacci number sequence and discuss how we solve that problem why we can kind of write this as a dynamic programming problem and then how we optimize the solution using dynamic programming then i'll get into a much more advanced example so stick around if you already understand this example anyways the fibonacci sequence of numbers is a very famous sequence that looks like the following we have 0 1 1 2 3 5 8 13. and then we continue now just to write this out here this would be the zeroth number first second third fourth fifth sixth seventh and then so on and so forth so if i were to ask you to find the nth fibonacci number so we have some function here say like fib and we take in n and we want to know what the nth number is in the sequence well the way we actually determine what each number in this sequence is is we simply add the two previous values in the sequence to generate the next one so if i'm looking for the seventh fibonacci number i add the fifth and the six together and that gives me well 13. now same for any of the other numbers right so for say this one right here i just add one and two and that's an exception when you come to these first three values here because we have to have some starting values in the sequence but for anything beyond the second number you simply take the last number and the second last number add them together and that gives you the nth fibonacci number so the reason i'm showing this to you is because this is a great example of something that we can use dynamic programming to solve and the reason we can do that is because we can write the fibonacci of n as simply the fibonacci of n minus 1 plus the fibonacci of n minus 2. so this is our entire problem these are now two sub problems and if we solve both of these sub problems that will give us the solution to the main problem so as easy as that this is kind of a dynamic programming problem because we can write it in this way so whenever you're trying to determine if you can use dynamic programming you usually need to come up with some type of equation it might be more complicated than this but something along these lines where you're saying okay the answer to the main problem is equal to the answer of a sub-problem and maybe multiple sub-problems okay so in this case we're adding two sub-problems together but we could be dividing them we could be taking the minimum or the maximum value we're just utilizing the sub problem solution to actually find the solution to the main problem so won't drag on that explanation anymore now that we've looked at this i want to show you the kind of naive approach to solving this actual question right here so for generating the nth fibonacci sequence and then i'll talk about how we use dynamic programming to better optimize this solution so i've just put on the screen here a solution to that fibonacci problem i was just discussing and i want to explain to you why the time complexity of the solution is very poor and then how we can optimize it using a dynamic programming technique now theoretically you could say this is using dynamic programming and the reason you may say that is because we're utilizing the solution of sub problems to get the solution to the main problem however the issue with the solution that i have right here is as a very horrible time complexity the time complexity is actually big o of 2 to the exponent n now i'm going to draw a diagram to explain why that is but to quickly run through the code in case you haven't seen this before we take in some integer n if n is less than 2 we return n so just for the cases of 0 and 1 so we can return 0 and 1 respectively and then otherwise we're returning the fibonacci of n minus 1 plus n minus 2 and this is a recursive call right so i'm recursively calling the function with in this case let's say i had n5 this would be 4 and this would be 3 i would then have to repeat the code for those recursively and while i would get my solution so the issue with this is that if i do decide to say generate the fibonacci number of five or the fifth fibonacci number the recursive calls that i end up making is to four and is 2 3 right as i said i need to call 4 and i need to call 3. now from 4 i need to make a call to 3 and i need to make a call to 2 because if i pass n equals 4 here will it generate the 4th fibonacci number because this is not a base case i must generate the third as well as the second right so you get the idea here i'm just drawing out kind of the tree of all the recursive calls that we're going to have from the third number however i need to generate the second fibonacci number as well as the first fibonacci number from the second fibonacci number this is not a base case i need to generate the first and the zeroth and add those together from one this is a base case so i simply return what the answer is now from two same thing i need to generate one and zero from three i need to generate two and one and then from two let's draw these a little bit weird here it's gonna be one and zero so sorry about the messed up tree on the right hand side but you get the point this tree is growing exponentially and if i actually go in here you can see there's a ton of repeated values that i'm calculating i'm calculating one a ton of different times right zero a bunch of different times two i'm calculating multiple times as well three i'm calculating multiple times and while this is leading to a very poor time complexity of big o of 2 to the exponent n because i'm doing a bunch of repeated calculations that i've already done as soon as i calculate say the second number i really should just store that value so i'm able to quickly access what the answer is same thing with 3 i should store that same thing with four i should store that i should never have to do any of the right hand side of this tree here because i should have already had the solutions i shouldn't have to actually make these recursive calls so i understand it's a little bit confusing for now but let me show you a new solution here that uses dynamic programming and then you'll understand kind of the basics of this approach all right so i've just placed a new solution onto the screen here which has a much better time complexity this actually has a time complexity of big o of n and the reason for that is we're using a technique here called memoization which is something you do typically in dynamic programming problems so as i said before there was really no point in us continually making the same function calls the same recursive calls to calculate a value that we already calculated previously so here we're optimizing our solution by implementing a cash now what is a cash well cash is just a way to store values that we've already calculated before so in this solution we're never going to do any repetitive calculations and that means if i want to generate say the sixth fibonacci number it only takes me six total computations to generate that or approximately six a linear number of computations so let's just run through this solution and see how it works because this is the most basic example i can give you of implementing a dynamic programming solution so we have our base case again inside of this function so if you have n less than 2 okay we're going to return n otherwise though i'm going to check if n is in my cache now the cache is simply a dictionary we're going to have different keys mapped with different values and every key is going to be one of the nth fibonacci numbers and then the value with that key is going to be the actual number associated with that so maybe we have 0 1 1 1 2 1 3 and then this would be 2 right so on and so forth that's what will actually be in our cache and i will generate this cache or kind of write it out as we go through this solution so we have if n is in cache then return the cache at n so this avoids us having to do any repetitive recursive calls because if we've already generated a value it will be stored in the cache and then what i'm doing here is exactly what i had in my previous solution except this time i'm storing the solution to whatever the call was to end here inside of my cache so that i never have to generate it again and then i'm simply returning whatever the value it is that i just stored in the cache so for example purposes here let's say n is equal to 5 again and now let's draw out the tree and see how large the tree gretz gets in this solution sorry as opposed to the previous one so if we're solving the fib of 5 well the first thing that we're going to see here is that it's not less than 2 and it is not in the cache and so we are going to have to generate the solution to this sub-problem so we're going to have to call 4 and we're going to have to call 3. so let's draw that out 4 and 3. okay so now we're going to go to 4 and we need to solve the problem for 4. so if we say n is equal to 4 it's not less than 2 and it's not in the cache so again we're going to have to solve these sub-problems we're going to have to call 3 and we're going to have to call 2. okay so now i go 3 and i call 2. now let's do the call to three so we come to three it's not less than two not in the cache we gotta solve these problems two and one so we have two and we have one and then what happens is we have two here okay we need to solve 2 because 2 is not a base case and it's not in the cache so we're going to call 2 with 1 and 0 running out of room but you get the point that's what we're calling it with okay so when we get to 1 and 0 we're going to return our values we're going to get 1 and we're going to get 0. so now what's going to happen is we've returned these values and we're going to say the cash at 2 is equal to and then this is going to be 1 plus 0 which is simply equal to 1. so now i have my cache and inside of my cache i'm going to have 2 which is my nth fibonacci number and the value of this is going to be 1. so now whenever i try to solve the sub problem of 2 again i'm not going to have to actually call these i'm not going to have to solve 1 and 0 i'm just going to simply take the value from the cache because now it's stored inside of there okay so now we've completed this recursive call at 2 1 is simply a base case so we return the value here that's going to be 1. this value is going to be returned as 1 as well i apologize this a bit messy but hopefully you get the point and now we're going to say the cache at 3 is equal to and it's going to be 1 plus 1 which is 2. so now i'm going to change the cache so now in the cache we're going to add key 3 and it is going to have value 2. so now whenever we try to find what the n fibonacci number of 3 is we'll be able to do that very fast we just take it from the cache okay then we need to solve 2. so now when we go to try to solve 2 i don't actually need to call 1 and 0 and the reason i don't need to do that is because 2 is inside of the cache so since 2 is inside of the cache i've now just avoided doing 2 recursive calls and what i do is simply grab the value from the cache which is 1 and i can return that up to 4 which is what needed that value so we're going to return 1 there and then from over on this side we're returning a value of 2. so now when we get the 4th fibonacci number we're going to say the cache at 4 is equal to and then this is going to be 2 plus 1 and that's going to give us 3 so we're going to insert this into the cache so we're going to say okay 4 this has value 3. and now same thing whenever we try to solve the sub problem 4 again we can just grab the value from the cache as opposed to actually doing those recursive calls now finally we go to this recursive call over here which is for value three and for three it's inside of the cache so i can simply return the value so i return the value of two from four we know this number was 3 and so we know now that the 5th fibonacci number is value 5. we add those together we would actually add it to the cache and then we just return the value from the cache hopefully that explained how this worked but what we were doing was storing the solution to each sub problem as we went and that avoided us having to do a bunch of recursive calls that we had to do in the previous solution and if we wanted to reduce these even more we could start the cache and say okay cache is equal to then we could have something like 0 1 and 1 1 but that would effectively give us the exact same solution as just having if n is less than 2. but we could remove this if statement and simply add these values into the cache as well just noting there's kind of multiple ways to go about solving this all right hopefully that makes sense but you've just seen an example of dynamic programming we've used a technique here called memoization now this is a technique that's used for dynamic programming problems or within a dynamic programming solution and all it involves is storing results that we've calculated in the past so we don't have to calculate them again all right so that is the first thing that i want to show you the first example i wanted to go through hopefully that is all clear now we're going to get into a more difficult problem and i'll give you a chance to solve it on your own and then i will walk you through the multiple solutions and different ways to go about solving it one of which of course is going to use dynamic program alright so i've just written an array on the screen here or a list whatever you want to refer to it as and i'm going to ask you the following question i'm just going to verbalize it so just listen think about it and then i will talk about how we solve so the question is determine the minimum possible sum of any continuous subarray in this array so what that means is that i could have a subarray say like this this is a continuous subarray because all of the elements are adjacent to each other i could have a sub-array that's these elements i could have a sub-array that's just one single element but they have to be touching i can't have a subarray that has say this this and this that would not be a continuous sub-array so they just have to be touching hopefully that's clear but any continuous sub-array what is the minimum possible sum of any one that we have and for this example right here the minimum sum that we would have of any continuous subarray is negative 7. now there's two possible answers here the first answer is to take this as the sub-array the second answer would be to take this as the sub-array if you take the sum of all the elements within these you'll see that they both add up to negative seven so that's really the question i'm asking you determine what the minimum possible sum is of any continuous sub array in an array so take a second if you want think about how you would solve it and then i'm going to show you the naive approach that does not use dynamic programming then we will talk about the dynamic programming approach so hopefully you've taken a second to think about how you would solve this problem because i'm going to go through a solution now this solution that i have is the non-optimal solution it runs in a time complexity the big o of n squared and this does not use dynamic program now this solution simply says what i'm going to do is find every single subarray in this array and then calculate the sum of all of those sub-arrays and determine what the minimum sum is that's it so we start by calculating all of the subarrays that start at negative seven calculating the sum for all of them and then updating this min sum variable then all of the sub-arrays starting at 3 then all of the sub arrays starting at 4 all of them starting at negative 2 so on and so forth and we get every single sub array that we have calculate the sum update this variable and well that will give us the correct answer now this solution is fine it does solve the problem there's nothing wrong with this the issue is that it runs in n squared and there is a faster and better way to solve this problem that involves using dynamic programming so what i want to ask you now is if you came up with this solution can you think of any way to solve this problem in linear time and at this point i will mention if you're unfamiliar with time complexities i do have an entire video on them so i'll leave it on the screen here and in the description anyways think of a way that you can solve this in linear time or big o of n time utilizing dynamic programming now you may not be able to come up with it that's totally fine of course that's why i'm here i'm going to explain it to you but just take a second and think okay can i solve this in a more efficient way so the answer of course is yes that's why i'm using this problem but let's get rid of this and let's talk about how we would actually frame this problem as a dynamic programming problem and how we would write a solution that utilizes the solution to sub problems so when you want to solve a problem using dynamic programming again what you really need to think about is what sub-problems am i going to have and how are the solutions of those sub-problems going to help me come up with the solution of the entire problem so i've just written a new example here and i'm going to start walking you through how we solve this using dynamic programming now in this example we want to try to solve this using one single pass of the array so rather than writing an algorithm right now let's kind of try to do this as a human and figure out what values we're going to want to store and how we're going to optimize the previous solution so again we only do a single pass of the array and there's no need to have a nested for loop and an n squared time complexity solution so what i'm going to do is start here at this element and i'm going to have some variable here i'm going to say min sum and this will be equal to 0 and this will just store what the minimum sum is that i've found so far and what i'm trying to do here again is create this minimum sum sub array or actually determine what the minimum sum is of any subarray so i need to kind of build different subarrays as i go through here and determine what their sums are update this value and then figure out essentially what elements i want to be in this subarray okay so i start at 20 we can kind of imagine that we can't see any of this right now because we're just looking at element 20 and i'm going to ask at element 20. what is the minimum possible sum that i can create using this element so at every single element the question i want to ask is if i were to use this element what is the minimum sum that i can create in a subarray so if this element was in any subarray i don't know how big or small the sub array would be but if it was included 100 what's the minimum sum i could generate that's what we're asking so in this case at 20 we know that the minimum sum that we can make is 20. so let's just write this here and we'll update this minimum sum variable really this should have been float infinity or just infinity before and so this will now go to 20 because if we have a subarray that just includes this element right here well the sum of that is 20. okay now we move on to the next element negative 7. now same question here i want to ask if i were to include this element negative 7 what is the minimum possible sum that i could have now the way that i determine that is i need to look at the minimum sum of the previous element and i need to add that to the current element and then compare that to what the value of the current element is so we'd have 20 minus 7 that's going to give us a sum of 13 or if we did not include this previous element so if we were to start the subarray say right here then we would have a sum of negative 7 okay so obviously negative 7 is going to be a smaller sum so i'm going to put negative 7 there and i would imagine that okay if i had the sub array i would not expand my sub array to be like this i would just start my sub array here on negative 7. no need for 20. that does not help me or it doesn't make it any more negative negative seven however it does okay so we have negative seven now with the minimum sum that we found is negative seven and that's if we're just using a sub array like this again from here we wanted to see okay should we include any of the elements prior and we said no because if we did then it was going to make this a larger sum than just having the element itself okay so now we have negative 7 and i'm going to move on to negative 3. so now if i'm on this element i ask the same question if i have a subarray that includes this element 100 so we're going to end right here would i want to include the minimum sum of the previous element or just this element well if i were to take whatever the minimum sum is that i could have using this previous element so including the previous element right here then that sum would be negative seven and that obviously would make this lower than negative three so i would just write negative ten here we're comparing negative seven minus three and just the element itself negative three well what's lower of course negative 10. okay so let's erase this bar here so now we move on to nine and don't worry i will explain this again so it makes perfect sense let's just walk through the entire example okay so now we're on nine same question from nine if i were to have a sub array that included the element 9. would i want the previous elements in the array to be a part of it or would i want just element 9 well in this case i have 9 and i'm going to compare that now to whatever the minimum sum is that i could create by using the previous element so again really what i'm doing here from 9 is i'm looking at this value right here and i'm saying okay if i were to include the last element what is the minimum sum that i can create that uses the last element in a sub-array it's not just the value of the last element it is again the minimum sub that i can create by using the last element in a sub-array and we know that the sub-array with the last element is negative seven and negative three so now when we come to 9 we say okay well if we're going to use this element in the subarray do we want it to just start here or do we want to include potentially some other elements well i look at this negative 10 i say well that's less than 9 it's going to make this smaller so of course we're going to include that and now the sum that i can create at 9 is going to be negative 1. now i'm not going to update my minimum sum and in fact the minimum sum should be negative 10. sorry i should have updated that before because well negative 1 is not less than negative 10. okay now i move over to negative 4. so from negative 4 again we have the same question should we include previous elements in the array well if i include this previous element right here i know that the minimum sum i can generate that uses this previous element currently is negative 1. so that means i can say the negative 5 is going to be the sum right here and that's of course going to be lower than me starting the sub array right here of just negative 4. okay hopefully this is all making a bit of sense continuing we'll move over to 6. now from 6 i ask the same question okay should i include the previous element if i'm going to have this element in a sub-array or should i just start the sub array right here well i want to include the previous element because negative 5 is less than 6 so that's going to give me a sum of 1 right here for this element no need to update max sum continuing here we're now at negative 9. now at negative 9 i ask the question is it helpful to me to include the previous element which is going to be 6 or do i start my subarray right here well the answer of course is no i'm not going to include it i'm going to get a sum of negative 9 and i'm going to start right here with this element because the minimum possible sum that i can create using this element with all of the previous elements that i have in this array is 1 and 1 plus negative 9 gives me a larger value than the negative 9 itself so i just start at negative 9. okay lastly i come over to 10. now the answer here is just going to be 1. of course we're going to going to include negative 9 because that's going to make this lower so now i actually know that the minimum possible sum that i can create is going to be negative 10. in that there you go i return that answer now i know this is not crystal clear but really all we did at every single position here in this array is we ask ourselves the question what is the minimum possible sum that i can get when i include this element in the sub array now the answer to that is it's either the element itself or it's the element itself plus the minimum sum that we can get when we include the previous element because we need to have a continuous subarray so if we're including the previous element well whatever the minimum sum is that it can have plus our current element that's the minimum we could get if we included this element and that allows us to actually not need to keep track of the different indices of the subarrays but to determine the minimum sum by constantly updating this min sum variable as we run through the problem now the dynamic programming aspect of the solution is that i am storing the solution to every sub problem that i solved and i'm simply taking the minimum of all of the solutions that i had right so all of these sub problems i need to solve i solved them one by one and they actually utilized the solution to the previous subproblems i then take the minimum of all of those sub problems and well that gives me the solution to the problem so let's clear the screen here and let's have a look at what the solution actually looks like in code all right so i've got the solution in front of me to find my function i have my if statement so just handling an empty array here and then i'm saying the min sum using element is equal to array at zero so this is what we're going to use to actually store all of these sub-problem solutions and then the minimum sum well this is going to give us the complete answer because we're taking the minimum sum of any of the sub-problem solutions okay we then continue here we say 4i in range then we're looping through all of the elements except index 1. our accept index 0 sorry because we've already handled that up here and then we're going to say the number is equal to array at i and we're going to generate what the current minimum is that we can create using this element so the minimum possible subarray sum we can get that uses the current element that we're on as i said that's going to be the number let me draw this in a different color here or the number plus the minimum sum using element at the previous index so if we were to include the previous element whatever the minimum sum is that we could create using that element we add that to the current element and we take the minimum of those two values okay we then say the min sum using element dot append current minimum then we say the minimum sum is min of min sum and current min then we continue this and well that solves the problem for us so this solution does run in big o of n time however it takes big o of n space because of the fact that we're using this array now some of you may have noticed that since we're only ever looking at the last element in the array we actually don't need to utilize an array and store every single sub-problem solution what we can do instead is simply store the previous sub-problem solution so let me put on the code for that and show you what that looks like all right so now this is the updated solution which is going to run in big o of n time and is going to take big o of 1 or constant space because we've now removed the array and instead we're just saying the min sum using the last element and this is not an array it's just whatever the last value was because we only need to access the last value again so we can just use a variable as opposed to using an entire array now let you read through this code but at this point i am finished with this video now dynamic programming on its own is not extremely complicated what's actually most difficult about it is determining how you write a problem in a dynamic programming way so how you frame the problem in a way such that you're solving sub problems so that's what i was trying to illustrate to you before when i was walking through the array step by step is that we can look at this problem and say okay the sub problem that we're solving is what's the minimum sum that we can generate when we include this element and once we start framing the problem in that way it now becomes very easy to figure out how those sub problems actually lead us to the optimal solution so that's what you need to think about when you're saying okay can i use this problem for dynamic programming or sorry can i solve this problem using dynamic programming you need to think what way can i look at this problem and kind of read it out such that i have sub problems that i'm solving and that's not always possible and sometimes you can solve sub problems but those don't actually lead you to the optimal solution so you have to rethink your approach anyways with that said i will wrap it up here hope you found this helpful if you did make sure to leave a like subscribe to the channel and i will see you in another one [Music] you