it would greatly improve your problem solving skills o coin change this one is a difficult one dynamic programming is by far one of the hardest concepts of all time dynamic programming is sometimes used but man is it difficult coin change is so hard what even is dynamic programming it's loaded with a thousand different terms recursion iteration top down bottom up memorization tabulation and every solution you find has these massive trees and table that seemingly come from nowhere and even if you understand why a solution works almost every DP problem has an entirely different formula so you won't be able to just blindly copy and paste it's confusing it's intimidating and it's the boogeyman of the interview process but in my experience DP is just misunderstood when people I have taught learn what dynamic programming actually is they find it to be one of the most intuitive problemsolving approaches and often wish every problem could be solved with DP let's let's take a look at everyone's favorite introduction to DP Fibonacci you've probably seen people draw it out as a tree and point out that there are duplicate nodes and that dynamic programming removes them but I'd argue that the essence of dynamic programming is not about removing them but realizing that they never needed to exist in the first place it's all just a conspiracy big function has been lying to you this is not the natural way to visualize a recurrence relation this is just the way computers and you have been programed to view it as a task that calls another task a recurrence relation is not the same as a recursive function it's not a task it doesn't do any calculations it has no side effects it's simply just a definition we can see that the actual graph representation of the recurrence relation is actually much more Compact and this is the core idea of dynamic programming we can simplify problems with the recurrence relation and recognize that naive recursion is not our only option to calculate it recursive top- down memorization and iterative bottomup tabulation are the two implementations that address this but they ultimately follow the same idea recursive terms are values not tasks but I want you to see it for yourselves I want you to see why recurrence relations are so elegant and intuitive we'll watch me solve a problem as if I've never seen it before absolutely locked into the Max and hopefully by the end of this you'll have a different view of not just dynamic programming but problem solving as a whole feel free to pause or rewind at any time I know I will coin change two given an interray coins representing coins of different denominations and an INT amount representing a total amount of money return the number of combinations that make up that amount if that amount can't be made by any combination of the coins return zero I can assume I have an infinite number of each kind of coin and the answer fits into a 32-bit end sorry for the ASMR jump scare but pay attention to exactly what I'm doing here I'm acknowledging my place as a Zoomer with a low attention span and chunking the problem into parsable bits missing key information leads to huge waste of time so pay attention Okay so looking at examples in the first one amount is five coins consist of one two and five there are four ways to make up that amount they all sum up to five and consist of one two and five okay that makes sense example two shows there are zero ways because you can't make three out of any number of twos example three yeah okay tens samples are part of the problem statement if you understand it then it should be quick if you don't it just might save you half an hour okay time to summarize using an array vents count combinations that sum up to an amount moving on to observations these first two lines talk about input so let's look at constraints length of coins is less than 300 each coin is less than 5,000 and so is the amount so the length of coins is a small size and coins of I in amount is medium this one says that coins are unique so coins are unique anything else I guess coins are positive okay that means I don't have to worry about zeros or negatives which which could lead to infinite ways that means I also know that taking a coin always decreases the amount left here's where a lot of y'all go wrong I know observation can be boring and monotonous and we want to jump straight into implementation but instead of playing technique roulette it's important we keep our cool and stay patient and methodical even if a problem sounds familiar we should still confirm it with our observations before committing too hard return the number of combinations this is a counting problem maybe there is some combinatorics formula okay what does a combination imply in the first example 221 is a combination one 122 is not listed why is that it's because it's a duplicate combination so I need to find some way to avoid duplicates what makes two combinations duplicates they have the same elements then what makes them look different they have different orders two requirements means I have two ways to avoid them so how would I avoid same elements I could keep track of counts or something how would I avoid different orders I could just just pick any ordering and stick with it since any ordering is good I'm also allow to sort if I need to okay between these two options I don't really have any clear idea of how to keep track of counts and sticking to any ordering is simpler anyways so I'll try that one first two things here just because you understand a term intuitively does not mean you are aware of its implications break it down second figuring out how order affects the input is extremely important for any problem it gives us a sense of direction and will make working through it much easier amount of money that can't be made I saw that in example two because two could go into three maybe divisibility or gcd could I come up with a way to figure out if an amount is possible with gcd sounds complicated I can think about it later I have an infinite number of kind of coin that just means I can reuse coins that also means I might need to know when to stop amounts can't be negative so I can just check before going negative the answer fits into a 32-bit int I don't care I'm using python all right let's review observation is the heart of problem solving many people reduce these algorithm problems as just pattern matching but you've got to be able ble to identify the patterns in the first place don't just randomly guess and check Solutions understand the problem break down keywords and get a sense of direction first observation requires a high attention to detail so stay organized and write stuff down you'll end up making quicker connections recalculating less and you'll reduce your urge to tunnel vision since you'll easily be able to revisit an idea okay I'll work on an example now I'll use the first one what is the decision I'm trying to make I want to find the number of ways to make five using 1 2 and five where do I start I can use any ordering so I'll just go left to right for now I can use a sorted ordering later if needed so starting with the first coin what are my actions let me think I really only have two I can take the first coin or I can skip the first coin what are the effects of these actions if I take the first coin I have to make 5 - 1 which is equal to four if I skip the first coin then I have to move to the second coin okay I've explored every Poss action to go further I would have to think deeper but I already have enough structure to start generalizing working on an example is a great way to build observations on a problem but we can do even better if we generalize it we'll be able to build observations that apply to entire classes of examples instead of just one I know this sounds intimidating and difficult but hopefully this next part shows how approachable and Powerful this can be so I'll do that by turning all these values to variables amount is going to be equal to well amount and coins is can be equal to coins what decision am I trying to make I'm trying to find the number of ways to make amount using coins I don't just want to start with the first coin anymore I want a more General position so I'll just call it I so starting with the icoin what are my actions so I can take the icoin or I can skip the icoin if I take the I coin I have to make amount minus coins of I based on my observations this could be negative so I need to check that coins of I is less than or equal to amount so if I skip the e coin I don't want to move to the second coin anymore I have to move to the i+ one coin okay let me look at this nothing really stands out so I'm going to think a bit deeper if I take the I coin then I have to make amount minus coins of I what are my actions I can take the it coin again or I can skip the I coin if I skip the icoin I have to go to the i+1 coin what are my actions I can take the i+1 coin or I can skip the i+1 coin I'm doing this take skip thing again so these subtasks have identical structure to my original task I can represent this with a recurrence relation pretty neat right working on an example is an extremely useful tool to give our initial observations more structure but we can turn simulation into formulation simply by playing around with variables instead of specific values often you'll find when you do this a solution or combination of solutions will reveal themselves to you I know that this is right I'm going to start coding I'm going to comment all of this out starting with a function signature I know I'm going to need to return an INT to figure out the parameters I just need to check what variables are affected by my actions so the take action affects amount and the skip action affects the coin index I so the coin index I and an amount will call X so it doesn't Shadow the amount given by the input then I need to come up with a name I need a descriptive one to make induction easy so I'm going to do num ways starting with the I coin to make the amount X yeah you saw that right I make snake case and camel case and wrote a name so long you might think it's proprietary but remembering what a function promises is key for inductive reasoning if everyone keeps their promise everyone will end up happy okay let's go with the recursive calls next if I take the icoin that's equal to the numb ways starting with the same coin I to make a smaller amount xus coins I I also need to check that we're not going negative so if coins of I is less than or equal to X we're good otherwise there are zero ways to take the only other action left is Skip so if I skip the I coin that's equal to the num ways starting with the next coin I + 1 to make the same amount X okay I need to handle the return value and since take and Skip are the only two actions that's just going to be the number of ways if I take the e coin plus the number of ways if I skip the e coin and this is the power of recursion and why we want recurrence relations we pretty much can explore all options just by simulating one level down I understand some of you may be skeptical but don't worry there are still laws that govern this magic so applying the inductive rule assuming my recursive calls return the corre correct value my function is correct when I read it out aloud but that's only one rule of recursion and I need to follow the other two to guarantee it one all my recursive calls must lead to a base case two all my base cases need to be correct I don't have any base cases yet so to figure out what base cases I need I need to look at where my recursive calls are going the take action always decreases the amount but since I have this if statement at some point I won't be able to take the take action so this acts as its own base case the skip action always increases the coin index by I so what's the largest valid coin index that's going to be the last coin index since I'm incrementing by one what's one past the last coin index that's the length of coins so I need a base case here if I is equal to the length of coins then I have no more coins to use so the only amount I can make is zero so so there is one way if my amount X is zero otherwise there are zero ways those are my only actions and they all lead to correct base cases so that's it I followed all three rules of recursion so this function is correct induction induction induction induction if you don't use induction there's no point in using recursion I know it's a scary math term but with a little practice you'll start to see how hard problems can be broken down into I can either take the coin or I can skip skip the coin you don't have to formally write it out in ancient Greek all you need to do is make keep and trust a set of promises also known as invariance take the recursive bleep of faith and just believe that those invariants will be upheld in your recursive calls and don't be a hypocrite make sure to uphold them yourself recursive code should be pretty short so just read the code aloud to debug which of the three sacred rules you are breaking don't ever think more than one level down and avoid resorting to print statements and simulating recursive execution if even computers get overwhelmed by Stu frames then your memory definitely is at risk for an overflow so all that's left is to solve the original problem which is to find the number of ways to make amount using coins and that's just the num ways starting with the zeroth coin to make amount one last thing this naive recursion is exponential and won't pass but because I know my recurrence relation is much more compact I I think we skipped the step where's the time complexity analysis I can represent this with a recurrence relation but if I want to represent this as a recurrence relation they can have side effects so what are the variables affected by each action take decreases amount and Skip increases the coin index I so the parameters are amount and I that means valid inputs for the coin index are 0 to length of coins and the valid inputs for amount are zero to the given amount any combination of these two might be valid so that means the size of the recurrence relation is O of length of coins times the amount how long does it take to calculate each state assuming recursive calls are values that have already been calculated I only need to look at take and Skip which are both recursive calls so in total 01 for the cached complexity the total time complexity is the number of unique states in my recurrence relation times the cash complexity so that's o of length of coins time amount times A1 I know that was quick but don't worry I got you let's break down what I did with the coin change problem I describ my state with two parameters the coin index I and the amount X we know our I is between zero and length of coins I'll just call it n for now we also know that X is between zero and amount so if we look at the total possible combinations of I values and X values we can see that it makes a nice little rectangle so the total number of terms commonly referred to as unique states is just the product of the two which is n * amount so now that we have the number of terms we just need to figure out how long it takes to compute each term obviously most of this function is O of one statement since we don't have any Loops but what about these recursive calls well the the rest of that computation belongs to some other term so we don't want to count that remember these recursive terms are values not tasks so we can treat the use of each one as an 01 operation I like to call this the cached complexity because we do regular time complexity analysis but we assume that the values of the recursive calls are already cached and are 01 and this is the formula for every DP problem it's just the number of unique states times the cached complexity I know y'all love pattern matching so let's solidify this with a little test I'm going to show you a recurrence relation give you the bounds of its parameters and I want you to tell me what the time complexity is I'll count down from three but you should just pause the video and take your time let's go here's the first one if you said o of n you're right despite having a third recursive call it's just another value so tribonacci has the same time complexity as Fibonacci under DP how about this one for the Catalin numbers the number of unique states is O of N and the cache complexity is also o of n so multiplying these together we get o of n s what about this one three parameter bounds each of size n leads to O of n cubed unique states multiplied by o of one cache complexity and we can can see that Floyd warshaw finds the shortest path between all pairs in cubic time final test definitely pause for this one we got two parameters that are both n so n s unique states we have an O of n Loop so that's o of n cache complexity so if you said o of n cubed you gave the right runtime however this solution is wrong in the for Loop you can see it modifies the board which isn't one of the parameters causing a side effect thus this can't be a recurrence relation and caching this will give a wrong answer this sodoku solver is a backtracking algorithm which backtracks changes it made for a failed candidate solution backtracking is not the same as dynamic programming hopefully these examples helped let's do a final review dynamic programming is not a single algorithm but a class of algorithms that break down problems with compact recurrence relations despite what the callstack industrial complex wants you to believe these can computed without naive recursion and Computing each term becomes way faster when treated as values not tasks dynamic programming is a confusing name and that's by Design so to help amend this I've renamed DP to decision parameterization because the entire game of optimizing with DP is how do I make a decision deciding the best deciding the number of ways deciding if something is possible with the smallest size of parameters DP requires you to make a new algorithm every time which is why it's so challenging and so rewarding it's actual problem solving if you focus on making solid observations then a lot of these problems are just as simple as simulating it out we introduced a ton of Concepts so feel free to watch this video again and give me more views anyways I hope you enjoyed it so let's wrap this up I need to make sure this will pass and is under 100 million Ops I'll have to check the constraints amount is 5,000 the length of coins is 300 substituting these into my time complexity that's 5,000 * 300 * 1 which is around 1 million that's well under 10 e so it should pass even in Python I know that this is right if I force recursive calls to be treated as values that are calculated once by caching the solution will pass thanks for watching this video is already dense enough so I'll save the conversion to iterative the space saving trick and comment optimizations for the next video like subscribe and hit that Bell notification as I like to deliver quality over quantity feel free to gatekeep but I'd love if you shared this video as my dream is not to just teach algorithms but to push the industry towards thoughtful problem solving and away from Brute Force memorization anyways good luck and go solve some problems