CodeCamp Day 15 | Diving Deeper into Dynamic Programming

foreign [Music] [Music] foreign [Music] okay so hi and welcome to Geeks for geeks today is the D15 of code habit and today we would be doing some more DP so the past mentors when I started off I did this and now some other people like devashish gaurav and some other mentors are also continuing this so if you don't know what is this all about this is all about making you habituated with the coating where you would be coding continuously for the next 21 days and then after 21 days just to keep up with the Habit you can start giving contests or you can solve more if you're not well confident enough so can I have a quick one in the chat if you are attending so that I just need know the names itself so hyper one how are you so so just let me know if the audio is not clear I would make sure that the audio is clear so let me just start a new note and this looks fine and create templates so let's have a dark template hmm this looks good and this is good okay thank you so much okay so hi aroshi uh many people tell me that instead of coding we love to listen your talks cello um so the very first problem we would be doing up is count the number of hops okay and then the very next one is egg intestines now before we move forward let me just tell you some things so if you are a person who has started off with dynamic programming consider first coding the recursive solution then memorizing it and then writing the tabulation approach and day by day when you gain confidence you can directly start off with the tabulation not again you can just skip out the recursive and the memorization part because the chances of mle error gets reduced a lot if you use so you can just see the problem quickly I would just share the screen itself okay foreign okay just quickly give it a read the number of people absolutely less so it should take a little bit of less time to read and say okay so I would be waiting for the next one minute so I would be just explaining the thing in general so basically this is a variation or I can say this problem is inspired from at coder DP contest where what is this all level add coded DP contest is considered to be a very good resource for a person who is learning dynamic programming okay but at this point you shouldn't consider solving all the problems just consider solving the first four or five problems and if you are done with these or problems okay because these are problems have an explanation out there in the internet so if you are stuck up you would know how to write DP and other stuff so this question is basically the Frog can jump one step like one step at a time two step at a time three step at a time so a real life scenario would be this is foreign ERS and our father was taking one step at a time and we started skipping stuff okay and we got happy that I am able to overtake the of my father I don't know how many of you have done this but I did this a lot and I have seen many people there okay so this is all about let's say the one jump is like your father the two jump thing is like your sister and the three jump thing is like let's say your small sister okay because she is much smaller and she likes to be fuzzing around everything okay mm-hmm no let's start this part of [Music] okay para test case n is equals to 4 and the value is seven okay n is equals to 4 and the value is 7 itself so now see first n is equals to 7. so from 7 if I take one step okay so let's say this is one step this is two step this is three step okay now let me just change the color this is stick by taking one step this is by taking three step two step and this is by taking three third step so we are told that hum look starting point so if I take one step the value remaining would be six let me just change the color this could be more appealing okay so let's say if I take one step again if I take two step at a time the leftover value is 5. if I take three step the leftover value is 4. now from each point I can start making decisions one more time okay so what I can do is I can again take a step of one two and three one two and three one two and three okay so now the values can be one two three one two three one two three teachers so if I take one step again it would be again five it would be again four it would be again three if I take one step let's do before again so it would be three five minus or three particle yeah it would be two four is a one part earlier so it would be three and four main two particle here it would be two four minutes remaining value would be one okay fair enough now let's take the last not last okay so see we have one two three we have one two three okay so if I take one step again it would be again four okay let me just change the color this would be four this would be 3 this would be two this would be one and this would be 3 again this would be 2 again and this would be 4 minus 3 is equals to 1. now take a screenshot of this and then you can just do it on your own I would be doing it for n is equals to 4 because otherwise the value would be very like the three recursionary would be very messy so I'm look for say start cutting I can take one step two step three step now let's see this so one two and three if I take one step kidney value is remaining would be two if I take four the value remaining would be one now the values again we can take three step at a time okay fair enough and then we have one two three one two three one two three okay okay so if we remove one from three the value would be two the value would be one three makes a three here the value would be zero two makes a one here the value would be one two matches together value would be zero so just let me see if I'm visible or not [Music] foreign there is only one step remaining so we can't really take a step of this and this okay we can't really do that now from here from 2 I can take one step I can take two step from from one I can take only one step from one I can take only one step okay one year again it would be one two method two together value would be zero one minus one is equals to zero and one minus one is again equals to zero now we can again take a step of this and we can just have it zero so up how many values of zero are we able to attain we are able to attain one two three four five six seven so we are able to attain seven ways like seven three cases this is not considered like let's say there is one only one step remaining this is not the scenario that let's say only one step is remaining and I jump I take a three-step jump and I just bang into the door okay like I don't know how many of you have seen But CID they are used to do this okay fair enough so classical series I don't know only people who don't know how many of you will relate this but it's nice this is all about this so what we can do is this would be the kind of tree that we would be doing this now give me a quick zero or one in the chat and let me just see just give me a quick warn in the chat yep n is equals to four there are seven ways to reach that value okay this was the test case now let me just check can you quickly like the video please I'm done okay what about arushi and all arushi and all of the people who are there for very initial period of time like they joined the class in the very initial period and they are still continuing that's great to be honest okay fair enough okay so this is how we can take a jump okay so yeah let's see this again [Music] so we have this kind of structure so what we can do so so this looks like what this looks like a recursion tree okay this basically is something known as okay this is drawing out the recursion tree and how I come to the conclusion that as a Precast structure if you are not familiarak is try to find an algorithm which would solve this basically the from if we stand at a particular position we have three path and then from that three path we have again three path it is just like the scenario like whoa um greedy stories okay let me just see if I'm visible or not still okay fair enough so oh greedy stories okay so basically this is kind of the same scenario from 4 we can deviate to three path that is one two three that can again take three part that can again do three part so basically we need to explore all possible ways okay we need to explore all possible ways and we need to return the valid ones what are do you mean the valid ones because translating the same in Hindi because I didn't repeat that in Hindi so that greedy Hatcher one the the person takes up an end he keeps the latest pocket and he thinks that it would be form inside the pocket and then that egg would be a hen the next day and that hem would produce two egg and that two egg would again be that thing just like just like the cell reproduction okay like one cell one cell would give birth to two cell two cell would give birth to again four cell four cell would give birth to again each cell if each cell is producing two cell at a time okay so if we have this kind of thing in our mind the very first thing that you should think of is nothing else than recursion okay so from each point we are getting three branches okay in the worst scenario three we don't have more than three options three options neither it would be more than three options three options like let's say the value is two so we have the option to just take one step or two steps but we don't have the Liberty to take the third step okay foreign okay so from each point we are generating three okay so the time complexity would be exponential for sure because time complexity does not permit us why because the time expected time complexity is how much the expected time complexity is Big off n but I'm not exponential okay High Valentine like I don't really know how to spell your last name sorry about that man I'm extremely sorry fair enough so up we have we need to do something more so we need to optimize this recursive solution so the optimization of recursion is nothing but dynamic programming so now we come to the conclusion that dynamic programming is required but what kind of dynamic programming is required dynamic programming much recursion very first thing is the base case Okay recursion so base case can be found out from the branches okay so if the value becomes 1 then we need to add 1 to the answer so if the value is 0 we need to return 1 to the answer because I got 0 1 here that means somehow by taking some branches we are at the starting point or finishing point if the Non DOT finishing point now less the number of ways to travel this now the very next thing is if we have just only one okay we we have just one then we can do it accordingly so if the value is 2 we can take one and then again one and then we can take one okay so hamare pass if the value is 2 so we have two options if the value is one we have just one option okay now up the very next thing is the recursive case recursive case just analyze the branches that are coming out from a node okay so analyze the branches that are coming out from there okay so from a particular node the value would just decrease by one two and three so what we can do is the record the recursive case the recursive case can be n minus 1 n minus 2 and 10 minus 3. okay these are the recursive case a recursive case is up we can go back to this quoting the recursive solution and then we can think of KDP what is this DP all about okay and it will just code the recursive solution so am I clear with the recursive solution give me a quick one just give me a quick one if this thing is not clear give me a zero if this uh if this thing is okay foreign the scenario is same something like riding a bike okay so let's say if you are going on a straight road which is very simple to write then it is not fun but why is the places like ladakh ladakh bike ride is why famous because it contains some huddles so huddles okay it's for it's more fun to learn when you have a greater interest and fight inspect uh interest interest young man thank you so much man okay okay foreign so what is the feedback after this point because you are the people who were able to hold this thing for this loan so just want to know like I know many people who just entered due to this is stop sharing shut up okay so what are the small things we would do I don't know implementation time come let's say I thought of a solution and then I need to implement it okay and this is uh what this is an online assessment online assessment let's say I coded the solution you also put it in the same solution but if I'm submitting enough like before you I would be getting more points okay this is how the rank list son made okay so what you can do is instead of writing long long again and again what I would do is I want you to learn at this point okay this point yeah I would just write LL and I would Define as long run what is this all about this is just the meaning of this okay now we need to do okay I would do it later okay now let's start the coding part okay okay I would call that okay I can do that in this also but I'm just building up a wrapper function okay it is not important but you should know these icons okay and then you would say if we come down to the finishing point that means okay so I would say if n is equals to equals to 0 I would say return one from this point okay and then I would say if n is equal to equals to 1 that means a key Series so I would return one so let's make this okay I would return one me now I would just copy the same thing to teach you the importance of copy pasting yeah okay n is equal to 2 so up this is a two way so I can take a jump of 2 I can take a jump of one plus one so I know b is all small cases I don't want processing for these or small cases okay now we would say long long answer is equals to the summation of all the three branches so we would say solve you have to directly yeah correct okay rack of n minus 1 I can pick one step I can take two step rack of n minus 2 okay plus work of n minus 3. okay and this is the and we would return it as the answer itself and now let us just call this okay so return rack of an okay return rate of this is done so now tell me if this small code is clear to you or not we are learning DP but up till now we have just coded the uh foreign okay like yeah you took efforts but it means a lot when you see at this point also I am also taking some efforts okay I'm taking some efforts you are also taking some efforts and we both are growing okay I'm also learning the discipline of working in weekends and you are also learning the importance of hustling in weekends great man okay thanks a lot okay fair enough and now see we need to optimize this okay so optimizing this is very easy okay you have learned about this but still I would just say you that recursion optimize okay so let us first understand why do we do this I don't really know if you have been explained this or not but still I would just explain you again okay so I got up is [Music] see if you watch this thing then you would see a different scenario okay the scenario is let's take yeah see I'm calculating here the value for 2. here I am calculating the value for 2. here also I'm calculating the value for 2 okay and any other places where I'm calculating the value of 2 no not yet and here I'm calculating the value statement very different color choose yeah one yeah okay and here also we are processing three okay so if the tree is more that is why I drew 7 if the tree is more processing the same thing again if You observe we are calculating 4 here we are calculating 4 here again okay let's do that the next thing in Red so see three here it is getting calculated here it is getting calculated here it is getting calculated here it is getting calculated here it is calculating calculated so let's take this scenario okay so just this scenario would be very good scenario okay this scenario okay so let's say I found a girl interesting okay let's say I'm still my college days I found a girl interesting in my class okay and then I tried to explore that girl okay I made friendship with that girl and then now we found out that we are very opposite to each other okay like our wives really don't match okay like she is a hater of which like non-veg and I just love not much okay I am a gamer person and she just hates Kingdom I'm a I'm not a movie person she is a very freaking about like she freaks about movies okay a lot so oh why didn't match so I just traced back and started on my own okay so now now I know that this girl doesn't have the vibe of me okay our Vibes don't really much okay so I need to remember it so that I don't repeat the same mistake I don't I shouldn't again try to explore her okay because I already should know that she doesn't hold the Y but y But If You observe here this recursion is kind of this kind of person who goes back to the same girl in spite of exploring like ef3 Explorer three calculator foreign [Music] that this thing is known as overlapping sub problem okay overlapping sub problem okay if suppose you are given a DP problem and you are able to show that a same thing is getting calculated again so it is observed that it is overlapping some problem then you are applying DP by Fab you would get selected for sure okay so try to be very good at this okay try to learn the like art of explanation also because at the end you need to explain to your interview your approach also and why did you really use you have just memorized all the solutions okay you should give proper reasons for it okay so this is what you need to remember but in the back end of your mind where you are processing this data remember the example of that boyfriend girlfriend like Siddharth has already explored some girl okay yeah funny example this would help you a lot okay so at this point we come to the conclusion that I need to remember something okay because recursion coffee reputative Tasker Okay so what I can do is if I'm not able to remember something so what I would do I would write somewhere that fill water so in the same manner we would write somewhere in something like memo memo pad or something so in the same manner we can save the result in uh variable or an array or variables like array collection of variables arrays and then we can access it from there so let's do the same thing okay just tell me if this thing is clear to you or not overlapping some problem what is this basically overlapping sub problem just give me a quick one key yeah consistency is a new flex after attending the this code camp oh done each other okay so what we can really do is we can save the result in an array of n plus one so at this point what we would do is we would see say oh yeah okay so I would make a vector of long law okay name it as memo okay name it as memo because so that value n can also be processed and then I would initialize everything with minus 1 y minus 1 because minus 1 as a value answer calculated okay suppose I see the memo pad and I don't see anything that means I don't need to do anything in the same manner I'm initializing everything with minus one this just tells us that this value is not initialized okay otherwise we would have some garbage value but we don't we won't be able to access like if we initialize uh array okay in the local space Global space [Music] okay so if we initialize anything in inside the globe local space that value gets initialized to the garbage value so to make sure we don't really concern about garbage value we initialize everything with minus one foreign give this the access so vector of long run and pass by reference okay what do you mean by pass by reference like learn about pass by value and pass by reference it would help you a lot so before calculation okay directly calculations of I saw a girl now before exploring I would just see my memo pile if I've already explored that coil or not okay so what I would do is if DP of n is not equal to minus one okay return DP off and itself okay and after processing suppose I have explored that girl she is not of my same way so I would write it in a memo type so before moving forward I would see if that value DP of n is equals to answer this is done now just compile and run and see how many errors are we making we would be making errors because we are not passing the BP thing and then still we would be guessing errors because we have one more thing to handle and here also DP thing needs to be passed and see how many errors are we making oops this is memo foreign actually we have an habit of calling this as DP you can also just write it as TP many people do it now if we just submit this you would get a wrong answer because the answer can be very large so we need to return modulo 10 to the power 9 plus 7 so I have already taught you that a plus b whole modulo is a modulo m plus b modulo m and then whole modulo m foreign capital M one one two three four five six seven eight and then 10 to the power 9 plus 7. okay and then let's go copy and paste okay and then we would have this also enclosed and then this and see how many errors are we making okay okay so I will just copy this solution of myself share the tab instead [Music] of hops again share with you the solution that I have written um nothing is this thing clear can I have a quick yes or no in the chat please give me a quick one if this thing is clear so that I can move forward to the next problem and the next problem is a little bit different from this [Music] please discuss 10 complexity okay okay that is my job basically and no matter in complexity so see here we are making an array of n plus one and we are just using variables other than array so the time complexity would be Big O of n plus 1 but constants are ignored so it would be Big O off and it is what space complexity okay big of n would be the space complexity now let's discuss the time complexity okay so each value would be calculated just once okay we won't calculate the same value again so if for one element we are processing three back elements okay like what we are basically doing okay let's say we are starting at seven okay so we we are standing at seven well only we need the one like let's say n is equals to seven let's say n is equals to 7. so this if statement won't work this if statement won't work this if statement won't work and this statement X7 is not calculated so we would only ask the value of n minus 1 that is 6. okay this is what this is basically we would require the value of 6 n minus 2 it would be what we require the value of 5 and we require the value of 7 minus 3 is equals to 4. so for calculating the value of 7 we require the value of 6 5 and 4 and what we are doing we are adding arithmetic operation take constant time okay so eight value calculate we are just taking three values summing that up and then we are processing it so that for one one way one value we are doing three operations okay so for calculating one value we are doing three operations so for calculating n values if we multiply n on both sides it would be 3 multiplied by n okay so the time complexity would be n because constants are equal so it is nothing other than big or space for recurrence stack is not considered in bigger okay recursion stack only cheese is not considered this is okay so look let's move on to the next problem [Music] read this problem we have a dark mode let's just see the dedicated let's just see the dedicated dark mode and this is not looking fine mine one is better yeah this is better for me okay foreign optimized for constant stress yes it can be further optimized I'm just explaining you the most basic approach because I want you to get habitual what is DP what is this all about so if you are done just after reading the problem if I don't reading the problem give me a quick one in the chat hmm okay thanks a lot for you okay so we have the name as g double e k g e s e k a one operation is required of inserting yes between two is find written the minimum number of operation okay let me just show you what this is all about foreign so insert remove and replace [Music] login so see G double e k m g a s e okay so now the very first option we have look we would start from the back okay which is a circle so what we are allowed to do we just need to convert either of the string to each other okay like we need to make both the strings same this is let's say s and this is let's say S1 and this is let's say S2 our final agenda is to make S1 equal to S2 okay let's say if we have like this is a very good example let's say if we have something like Siddharth this is okay and this is something like this s i d d h u these are the names like this one like people like people from my school call me said though people incorporate call me said and some people do all also call me Siddharth okay like very less people call me okay uh okay so what we can do is so if I said those there so I need to remember this remove the CEO and I need to add a r t h a to make this as saddharth okay to convert Siddharth to said I need to remove this all values so this is how two strings can be made to each other by what by insertion by insertion by replacement okay replace U is replaced by a insertion replacement and what deletion this is deletion only let me just see delete only remove yep then okay and this is something like remove so these are the three options we can have either okay either there are three options you can have either to add the Masala either to change the Masala or either to eat without masala okay these are the three options so you can have so essay Piggy okay so now let's think of how to solve this problem so now if you see we need to make both the strings similar and we have K like is so what we can think of is see K is equal so take k out okay take this k out and you just process it for the rest of the string okay because now what we are we getting at this point if we remove this value of K we would be getting g e e and then we will be getting g-e-s-e okay now again we have the last character similar so again we can remove this okay we need to remove the Panic thing about e because E is good enough it is the same thing as the next string so you I can just take care of e and you do it for the rest like let's say you are cleaning up the room okay so what you do is like let's say you told your movement see I'm brooming up the floor and you take care of the rest of that okay so in the same manner I'm taking out K because both the values are K so it is good enough I'm just taking out K and saying kindly process the rest of the string K is equal again we have e we can take out this is okay so now if we take care e also then we would be Rift something like g e and g e s at this point we don't really have this options okay so now we have three options the very first one is insert replace and delete so if we insert this s to make both equal okay so that would be g e and this would be g e okay and we have used one operation so yeah operation is if we remove this s then it would be again GE and GE and again if we replace this value okay so replacement is not really an option okay we really can't replace it let's say we just made this e as s itself okay so it would be if we make that as s so a s or a s same again okay okay so if we make this as yes then this SNS would be same so they would be removed so we would be left with G and G E and here also I have used one option okay if the last character is same we take out the last characters and say you do the you do the processing for the rest don't care about him okay don't really care about him I would take care of it you do it for the rest of it no If You observe that after insertion we have these things okay now again after an insertion we can see that this value is same so now it would be just G and G after insertion these two value is also same so we would again have G and G and these two values are not same so we would again have a processing so either we can insert a value that is g e and g e and we are adding one e either we can replace the value so this would be so like this would be replaced with replaced with e so that would be just blank here and this okay so if you can see this thing okay this is how we would be getting to the very bottom and last measure string that means everything is processed and just count the number of mistakes so what are we basically doing where first if the last character is same we are taking out the last character we are seeing process the rest of the string don't care about the last character okay if last character is not same to be problematically okay the very first one is very simple okay that is s of n minus 1 is equal to S2 of n minus 2 then we would say kindly just move forward okay this would be also one kindly just move forward so move forward move forward and remove the last character okay if this is not the scenario like let me this is the screen is freezed okay okay so if if last character is not equal if the last character is not equal then what we really need to do is either we can insert a character okay if we insert one character okay if we insert one character then this s is getting removed but the see we have a replacement for S but we don't have a replacement for this so only one string is would be less like let's say uh let's take the scenario let's say okay this person is having a homework of mathematics this person doesn't have any homework like let's say he also have a homework for mathematics he also offered homework for English he doesn't have an homework for English okay you don't know best friend now friends are very naughty okay they try to like like I need to work hard he should also work hard if you are a child so he told to the teacher let's see Siddharth like let's say my best friend told to the teacher said that doesn't have an English homework kindly provide him with the English homework so now Siddharth also another English homework so the home like now they both are done But If You observe Siddharth didn't make any progress earlier also he was having one homework after doing English also he's having one over but my best friend made a progress earlier he was having two homework and now Siddharth also has two homework okay so progress is so in the same manner if we want to insert something then we would say that S1 would be kept at its same position and S2 would make a progress of n minus 1. because the last value got replacement the last value is initial number of characters is still saying okay earlier this I had one over even after having English homework and completing it I am still at my current scenario only like previous scenario only ear also had maths homework now also I am not so much I just did a little bit of extra work let's talk about replacement replacement is a very good thing why because let's say let's continue the same thing let's say I got a science homework and my friend got a I got an English homework my friend got a science homework is my friend he is my roommate so make both the homework equal so the teacher made both of us do the science homework okay because the replacement okay okay earlier also my best friend had two homework now also he has two homework earlier also I had two homework now also I have to homework okay so whenever we are whenever we are replacing something whenever we are replacing something it would be S of n minus 1 and this would also be S of n minus 1 both would do okay now the very last one is insert replace and remove okay remove remove but let's say it would be very interesting yeah let's say my friend has one more science homework I don't have it so now what the teacher did was my teacher said okay as your friend is not having signed so much you can also skip the science homework so now the progress has been made by my best friend so in the same manner we can say that remove is also one-sided as someone press 1 of N and S2 of n minus okay am I clear with insert replace and remove just giving a quick one [Music] okay just let me bring some water all right thank you okay see let's say my friend let's say my friend also has a science solver okay my friend has two homework to do and okay insert okay my friend has maths and science homework and I have just mathematics homework now he got jealous that said that needs to work less he is my friend how can I leave him alone best friends are like that so he told the teacher that Siddharth doesn't have a science or what teacher found out yes Siddharth somehow manipulated other people and he slipped off without having signs of work so what he did was now the teacher has detected Siddharth so he has now burdened him with science homework too my friend is very happy because AB he has gained something out of it but I am not happy because I need to do two homework you know now if you can see by doing this we have the last one okay we have the last two homeworks same so we can remove the last two homework but if You observe earlier my best friend has two homeworks and I had one homework so I am at my place only like I am still in my one homework but the workload of my friend has been reduced okay that is why insertion leads to the benefit of the next person not the first person okay okay okay foreign it is S1 of n and now let's just code this shell so yeah baby we would have a wrapper function to the return type would be integer the name would be red and then we would have N1 and input the sizes of both the string and then we would have the string itself string of S1 comma string of S2 okay okay I need to tell you the base cases okay the base case detecting the base case from there is a little bit difficult but I would just tell you the intuition of the base case what is base case base case is the smallest valid case that can be handled by you foreign okay the number of strings the number of values in the next string or what we can really do is we can add up this one two and three yeah maybe the value would be three why because the number Addis add insertion and remover both have the same voltage so if one string is empty that let's say if N1 is equals to Mt then we would just return the value of N2 just n 2 plus 1 because we would be operating on index so N2 so just return the value of M2 and this would solve the purpose okay shall now let me just share the screen itself okay now see if N1 is equal to equals to 0 will return into now if N2 is equals to equals to 0. then return okay so now if the last value is same so if s 1 of N1 minus 1 the last value of both of them is same n 2 minus 1. the last value same what we do is last character coming up this is just like if we have lot things like let's say my my roommate told me to clean the house so I just broomed everything and told you I'm taking care of the broom part brooming part and you can do the rest of the things if I found a similarity thing or if I found the last two character scene I would take care of that and I would say do this rest little process the rest of the string and just ignore this thing so what we would do is we would say answer it's like let's initialize an answer at this point and answer and I would say at this point answer is equal to rack of N1 minus 1 comma N2 minus 1 okay and then I would say S1 and S2 okay why do we really require that let's make string S1 comma S2 so that we don't really need to pass it again it can be just accessed from the top and here I would say s is equals to S1 p is equals to S2 okay this would make the code lot cleaner and this is just a matter of string so it won't hint the purpose so I would say this if the last character is not same then we have options to options to do what insert remove and replace and we need to have the minimum out of that because we have three options again three options we need to take out that minimum value so I would say Inc removal is equals to rack of wreck of break off N1 comma N2 minus 1 okay N2 is benefited if I just so remove removal removal removal uh if I just remove the last character either of it okay removal insertion ISD let's say insertion direct of N1 comma N2 minus 1. so removal what we did was removal is n comma minus 1. n comma n minus 1 n minus 1 done this would be just the opposite okay insertion because I'm seeing that I didn't take this so insertion camera okay like we insert a value at the top okay so that is why let's do the opposite of this okay and this would be N2 minus one now this is clear okay once the first value would get benefited once the next my best I once I would get benefited if the homework is removed and once my best friend would get benefited because now I have more burden okay now if the very next thing is replaced if the homework is replaced then we both would get benefited because we can cheat from each other so replace is equals to break off and 1 minus 1 comma N2 minus 1. okay and the value would be the minimum of removal insertion and replace so answer is equals to minimum of RN r m comma IST comma replacement basically just get this on curly braces because minimum allows you to have the minimum between two values but if you just conceal it in a curly brace it can take out the minimum of more than two values okay just a small bit of him okay then we have the return statement and then we would call from here okay return rack off S1 dot size and S2 dot size itself we'll just have it as N1 and M2 and N1 is equals to S1 dot size and N2 is equals to S2 dot X and let's just have it as M1 and N2 and the code would look a lot cleaner okay uh am I clear am I S one is equals to s okay S1 is equal to X I just take the opposite okay thank you S2 is equals to this is done now we can do a something more see if N1 is equals to 0 that means we are returning N2 if N2 is equals to 0 we are returning N1 okay we would do it at the end okay so now we need to memorize it because you can just see the recursion tree and we are doing the same thing again and again you can draw the recursion thing on your part so we need to do the same thing again and again So to avoid doing the same thing again and again we need to store it somewhere so what is the maximum value of N1 the maximum value of N1 is the size of the first Maximum value of N2 is the size of the second string okay so what we would do is we would make a DP array of size N1 cross and pick okay so we would make a vector of 2D vector Vector of vector vector or print and name it as memo and the value would be N1 okay N1 comma Vector of in in and this value will be N2 comma minus 1 so tell me that this value has not been processed okay but before processing we would just ask that the value is already processed only if memo of N1 comma N2 is already processed memo of N1 comma N2 if we are processing these values then before returning we need to save up this values is equal to answer okay we would save this value as the answer now we have N1 and N2 okay so now we need to pass this also so we would just say Vector of vector vector of vectors and then we have passed by reference as DP then we would pass here DP just copy this thing okay submit we need to pass this value very huge this one so now we need to pass the value here okay okay the DP has the access to everything we are making here the value of DP if it is we are initializing everything with minus one so the value is -1 that means the value is not calculated if the value is not minus 1 that means we have calculated some value okay we have some value that is calculated and see how many errors are we getting oh memo was not declared in this code tomorrow we would just use DP okay let's just have this as I know okay any more places where I need to do memo memo again yep here now religious company we won't use memory okay segmentation fault timeout solution dumb okay just let me resolve this if N1 is equals to 0 if N1 is less than equal to zero if N2 is less than equal to 0 greater minimum not equal to minus 1 and 1 comma into then return okay this one would be n plus 1 because we need to access the index N1 and into and then we would do N1 comma into I think this would be the error because we were accessing N1 but the N1 index was not present and yep now we have an output so update okay okay so we have used one operation so we need to add this value as 1 because whatever we do that would add as one operation that is why we are getting 0. so you can also learn this K1 plus 0 here that means the operations are not getting calculated so I knew that here I am doing a mistake so now I have the correct one okay fair enough I was able to do debug this real quick so I would just share my solution if you have any concern or queries you can quickly ask me but I can optimize this a little bit more to make this code look more cleaner okay I can make this code seem more clean let me just share the code first needs to be changed also done we don't have the if we insert yep it is also done pratik goli I just forgot it okay [Music] so now I can just make this a little bit go further what I can do is see n one zero and we're returning N1 into 0 and we are returning N1 so always we are returning the greater value so what we can do is we can simply say if N1 is equal to equals to 0 or RR N2 is equals to equals to 0 then we would just return the max of N1 comma N2 here let's say the max value N1 is equals to 0 then N1 is equal to 0 and N2 is equals to 5 so max of 0 comma 5 is equals to 5 returns yes if I can optimize this further or not okay a small small optimization I can optimize this further okay I can use bitwise operation now I'm just making this level go a little bit level I for intermediates I can just do something like this and then I can again just hit the N1 and N2 so when the value of N1 is equals to 0 that would be 1 its value is N1 value is equals to 5 and the not of 5 is not equal to not equal to 1. okay so if the value is 0 then not of 0 is equals to 1. okay so we are having a true value so that is how we are able to so this is a small bit of optimization if you want to learn to just clear up the Clutter okay like you can use the feature of global space so that you don't need to pass S1 and S2 again you can just initialize this memo also in the global space but you don't need to take care of writing memo again and again and the code will look much cleaner okay and you can write a type diff you can write a Define for this also I used to write this okay so now am I clear with this thing or not instead of Max why can you discuss tabulation bottom of approach also uh I don't think I should discuss because this is meant for beginners and at this point you shouldn't just code for tabulation at this point you should just focus on recursion plus minimization because recursion memorization gives you an idea of how this is working if you directly start up with tabulation every other people would start like every if you see the people out there on the internet they would start filling rows but how is that happening now you have the intuition that if the value of I is equals to 0 the value of J is equals to the value of J so initializing the base condition is very easy in recursion and memorization but you need to First process these two so that you learn the art of tabulation okay still I would discuss the tabulation approach option so see how we are doing that okay so we are taking N1 so what we can do is we can so if N1 is equals to 0 the value of N2 would be equal to N2 so I can just initialize a for Loop and say for end I is equals to so for end N1 is equals to so I can say for all I for I is equals to 0 the value of all J would be equal to that okay so I can simply do that okay then I can do this thing by using a formula okay I can just go back and hit that just by copying the conditions of this okay now do I make sense give me a quick one in the chat and I would be more than happy to bet farewell and I can enjoy by the way okay and watch some series or something and then it's done okay let's give me a quick one thanks okay sorry like there is a person also asked okay so that's it for today okay the last question hint for the third problem palindrome partitioning problem the last one is the palindrome partitional problem so that is a range DP problem so if you if this is the first time you are doing DP don't solve that problem if you are an intermediate the very first would be hint would be that we need to observe on the ranges okay is is point of time foreign okay and it is a hard problem to be honest I was not able to solve that problem on my own initial okay when I was when I was learning so that's it for today if you're watching this stream in the recorded version so just let me remove this so if you're watching this stream in the recorded version consider liking the video and commenting on the video for the reach of this video could be increased and this hard work could be justified if not if you are an introvert you can at least comment and drop a one in the comment so that it would be recommended more and this free habit thing free appreciative thing would be boosted up more so that's it from my side all the best to you guys and tomorrow I would be the one who would be taking this trip so I so if you want you can just start on that that's it for today everyone thank you