Lecture on Dynamic Programming on Grids

hey everyone welcome back to the channel i hope you guys are doing extremely well so today we will be uh starting with something which is known as dp on grits or you can say dp on 2d matrix or something similar to uh which has n rows and probably not m columns but similar to that is what we will be uh starting with so to start off with we will be uh solving problems how to count paths then we will be solving problem how to count paths with obstacles then obviously we will be doing something as minimum path sum now these questions are all asked in big big tech giants okay so right after that we will be doing something like max path some but this will be under certain conditions it won't be the standard way right after that we will be doing the triangle problem and after that again we will be doing one similar problem which will be having two start points with two people just to understand how to elongate so i'm very much sure after you do all these six problems because all these six problems are of different types if you have done all these six problems you can do any problem on dp on grids or on 2d matrix this is my promise to you so you just need to make sure all the six problems is what you need to watch and submit now i'll be leaving the code studio link out over there in the description you can definitely sum it over there just in case if you want any other platform you can just take up the questionnaire in the title and you can do a google search if you want any other links but but yeah i highly recommend you to try out code studio because it's a wonderful platform and something which is from india so we should definitely support it now what are the prerequisites for dp and grits i will highly recommend you to watch the lecture seven as i always say because over here i have taught you a trick where i've told you that if you're writing a recursion function and you have to count ways how do you do that you write a base case and in that base case you either return a one or either you return a zero depending on if your conditions are met or not and then you take whatever recursions you have like how many number of recursions and then you return l plus r so if you remember these uh ways that's how you count ways and the lecture seven have deeply uh taught you this so if you don't know about this please please watch it out because without this recursion on grades or dp on grids uh will not be easy for you so please watch it before starting off with dp on grits so to start with uh let's check out the first problem which is total unique parts now what are they saying uh they're saying you're present at point a okay which is the top left cell of an m cross n matrix top left cell of an m cross n matrix your destination is point b which is the bottom right cell of the same matrix something like zero comma zero will be the top cell and the bottom will be m minus one and n minus 1 for sure your task is to find the total number of unique paths from point a to point b in other words you will be given the dimensions of the matrix as integers m and n and it asks us to find the total number of unique paths from the cell 0 0 like the point 0 0 to n minus 1 and m minus 1 for an example if i give you a matrix of 2 cross 2 size the number of unique paths will be 2. let's understand this question in deep okay so if i'm saying that i'm giving you a 2 cross 2 matrix okay this is the 2 cross 2 matrix definitely and over here if i'm saying you you started this this is your starting point this is your ending point because if i write down it states from 0 0 to 1 comma 1 because that is the right bottom most cell so how can you basically move this okay now remember in the question it clearly states you can only move right or you can only move down no other movement is allowed only right or only down so if you move right you will end up reaching here and then again if you move right you will end up reaching here so that's one of the ways and i can see the other way is you can decide you will move here and you will reach out so i think there are a couple of unique ways unique ways in which you can reach from zero zero to one to one okay so if there are two two ways to unique ways you have to return me too so how do you do this problem now if you remember how to write recurrence that is something which i taught you how to write a recurrence that that is something which i taught you but before that we have to analyze why recursion right so what are you doing starting from something like zero comma zero and if i just write it in a generic way you're starting from zero comma zero and you're wanting to go till m minus one and n minus one that is what you are looking to do am i correct right i'm absolutely correct now can i say you're basically trying out all possible ways to go from 0 0 to m minus 1 n minus 1 all possible ways now whenever you try out all possible ways what have i taught you till now all possible these means apply requisition as simple as that because if you have to count all possible ways i'll try always and i'll count them as simple as that after that dp and all that comes afterwards but if i'm being asked to count always i'll try always as simple as that i'll try one way two way three way i'll keep counting in this way i can get the total number of phase right so that is what i'll do so what is the question how to write recurrence now in our one ddps i've taught you how to write recruits what is the step one express everything in terms of indexes remember this express everything in terms of indexes but over here instead of index what will you do it's a 2d matrix so obviously indexes will be two two indexes one is the index i which will represent the row number one will be the index j will which will represent the column number so slight change in the three rules over here express everything in terms of i and j where i is basically row number j is basically column number right next explore all parts or do all stuffs whichever you call it do all stuffs the point number two stays the same if i'm counting always sum up always if i'm looking for max or minimal i'll take the max or minimal depending on the question if you are being asked to count all the ways you sum up all the ways if you're being asked to count max and minimal you'll count the max and minimal okay depending on your question you're going to do this so simply follow these three steps and you can write the recurrence for any 2d grid and after that you know the steps are very easy to convert a recursion to dp to rather memoration and then to tabular db and probably after that to space optimization right so let's get started so what was the question the question was stating how many ways are there in order to reach from 0 0 to n minus or rather m minus 1 n minus 1 that is the question correct so can i say let's assume i write a recursion f of i j i write a recurrence f of i j where it tells me the number of unique ways the number of unique ways in which i can reach from 0 0 to i comma j specifically what i'm saying is if i'm taking a grid like this and assume this is my ij i'm asking in how many ways so what i'm saying is in how many ways can you reach from here to here so basically i'm trying to figure out the answer for this particular matrix that is what f of i j is signifying it's trying to figure out in how many ways can you reach from here to here if i and j is this right so where will we start off with we will definitely start off with f of m minus 1 and n minus 1 because this is f of n minus 1 and i want to find in how many ways can i reach from here to here so the entire matrix right so i can see i'll start off with i comma j where the initials of i comma j will be m minus 1 and n minus 1 this is generically how you determine where to start off with okay so that's what i've done what's the first step in recursion it's the base case right so if you remember if you remember the lecture seven in lecture seven i think i've told you how do you count ways in order to count ways you have to determine a base case that returns 1 correct so in the base case if you have reached your destination you return 1 or you return zero if you haven't reached your destination that's that's your base cases if you have reached your destination you return one if you haven't reached your destination you return zero that's what i've taught you in the lecture seven so why don't you do that over here so what i'll say is okay i know my destination is very straightforward if i'm starting from n minus one m minus one or rather the opposite m minus one and m minus one i will have to go in such a way that i reached this particular guy from here correct so i know this is the base case where i reach 0 and 0 so straight away say if i is equal to equal to 0 and j is equal to equal to 0 if that's the case i definitely know i have reached my b like the destination and if i've reached my destination i know the recursion would have taken a path and it would have reached here so why don't i count that path so i will say return one because on returning one it gets counted lecture seven guys lecture seven of recursion series okay so that's that's how you can easily count it correct now what is the other base case assume you are standing at m minus 1 m n minus 1 there is 0 0 and you kept moving up kept moving up kept moving up kept moving up and you exceed the boundary or it might be the other way you kept moving left you kept moving left and you exceeded the boundary so you can either exceed the boundary in the upper direction which means the row number row number goes lesser than zero or the column number goes lesser than zero very straightforward so what i can say is if the row number goes lesser than zero or the column number goes lesser than zero that path is something which is not a path because it took you out of the boundary and i wanted to travel inside the matrix in order to reach from m minus 1 n minus 1 to 0 so it you got out of the boundary right so what you will do is you will say i will not count this path this path is not under my account so i will return 0 make sense that's what i've done so the base cases have been written remember this these are the base cases that i've written so express in terms of index and write base cases that's a step one so what i've done is i've made sure the step one is complete what is this explore do all stuffs now what is all stuff over here let's analyze the question stated the guy can move in the rightward direction or in the bottom word direction so if you are moving from the bottom yes if you're moving from the bottom we can say it's opposite yes we can say it's the opposite if you're moving from here to here i can so the right one will be either you can move left either you can move upward it is exactly the opposite so if it's exactly the opposite just do because there are two ways one is up one is left instead of bottom and right over here it's up and left why don't you explore it so i can say okay i have couple of ways one is the upper way where i will say okay i will move to if i go up if i go up what happens the row reduces again very basic stuff the row reduces and the column stays same if i go left what happens the rows because if i'm going left we are still in the same row but we are moving a column back so thereby j minus 1 correct so we have done this and so explore all possible paths is also done what's the next step sum all the ways because you've been asked to count the total v's so kindly sum up all the ways so why don't you sum up all the ways so what i will do is i will say return up plus left so what i've done is i have returned up plus left so i've summed up all the possible ways over here and this is what a recurrence will be yes this is how you can easily this is how you can easily write a recursive solution so very straight so very straightforward express explore sum up or whatever is the question stated that's how you do dp on bits so since i've done this we have done recursion right and we know that for every index yes and for every index we are exploring uh two possible parts correct so i can say the time complexity of recursion how many ways are there like how many boxes are there in the matrix m into n boxes and for every box you're taking two two parts up left up left up left up left so if for every boxes you're taking two parts can i say can i say all the boxes in total yes all the boxes in total will be having 2 into 2 into 2 into 2 into 2 into 2 parts which is 2 into m into n parts so the time complexity is this which is exponential in nature right space complexity is a recursive stack space which will be uh the path length which will be the path length remember the space complexity will be the path length why because if you're wanting to reach here let's say from 3 comma 3 the path length will be you will go to two comma two then you will uh sorry or two comma three rather then it will go to one comma three then it will go to zero comma three then it'll go to zero comma two then you'll go to zero comma one and then you'll go to this so the path length contains one length two length three length four length five length six length so it's basically the path length is nothing but m minus one plus n minus one is the path length because over here you took if you see carefully over here if the length was four you ended up taking three upward directions and you ended up taking three leftward directions right thereby the path length is uh this so this is the recursions time complexity and the stack space complexity now what's the next step what's the next step in recursion i have told you easily how do you optimize recursion in order to optimize recursion what you generally do is you try to convert that into a possible dp solution correct and how do you do this in order to do this you try to do something which is known as memo i action correct but when can you apply memorization if there are overlapping sub problems yes if there are overlapping sub problems you tend to apply something like a memo iration so why don't we do that so what i'll do is i will take m equal to uh let's say three i'll take n equal to three and i'll try to figure out how many total ways are there correct so practically speaking this is how the grid will look and you want to find how many ways are there to reach from this particular position to this particular position right so let's do that so this is 0 1 2 this is again 0 1 2 so we start with f of two comma two correct now where can f of two comma two go it can either go to the upward direction which is definitely f of the row numbers reduces by one and the column stays the same or it goes to the leftward direction when the row number stays same and the column number reduces by one correct and if you know in recursion if this is the upper direction this is the leftward direction which recursion will be occurring first obviously this recurrence will be occurring first so let's do this recurrence now f of one two where can it go it can definitely go to something as f of zero two and it can definitely go to something as f of one comma one this is the upward direction this is the left direction this is the up this is the left now where can f of zero to go it can again go to the up so if it goes to the up it's minus one comma two and if it goes to the left it's basically zero comma one correct so what happens over here whenever you reach f of minus one comma two what happens over here so if you remember the moment the row goes lesser than zero there was a base cases i lesser than zero or or j lesser than zero if any of these things happen you end up returning a zero so you end up returning a zero over correct over here there is something like f of zero one again it can go up which is minus one comma one or it can go to the left which is zero comma zero correct so minus one comma one will again is the upward direction which will return zero and this guy ends up returning one because this is where your destination is because this is where your destination is you have reached f of zero comma zero so that thereby this is your destination so how will the recursion be like f of zero comma one would have called up would have called left so the up would have been minus one comma one and the left would have been f zero comma zero this guy gets one this guy gets zero and in order you return the summation of both which is zero plus one thereby this guy gets a value of one so i can say this guy gets a value of one so you can easily return that value one correct so thereby thereby let's quickly erase this and try to solve this recursion now here at f of zero two at f of zero to what would have happened it would have gone to up which is f minus one two which gave him zero which gave him zero it have gone to left which would have give uh gave him f of zero one which is one so thereby it returns 0 plus 1 makes it a value of 1 so it returns a 1. so let's quickly raise it so this is how it will be and in the next step yes in the next step what happens there is something like f of one two it goes up and now it goes left so f of one one will be something like f of zero one because it has to go up and similarly it will be like i have to go left which will be f 1 0 correct so if you carefully see we get our first sub problem 0 1 has been solved here so there is no need to go further down into f of minus 1 1 which is the top and there is no need to go to the left so i got my first sub problem thereby i see there are overlapping sub problems and if there are overlapping sub problems what can we apply we can definitely apply memoization and what is the shortest what is the shortest trick that i have told you to apply memoration just figure out which is the changing parameters so there are a couple of parameters correct one parameter was i the other parameter was j so if there was a parameter i which is changing there is a parameter j which is changing so what is the i's maximum value i can say it's m minus 1 because that is where we start the recursion call what is the g is maximum value n minus 1 because that is where we start the recursion call so i can say if i require the index m minus 1 i will have to declare an array of size m because if i declare an array of size m i will get the index m minus 1. similarly similarly in order to get an index n minus 1 i have to declare an array of size n so basically i can say i will be requiring a dp of m cross n which is a 2d dp of m cross n so if i have a 2d dp i can convert this into a memo iodization solution so how do you convert this into a membranation solution again very straightforward step one declare the dp declare the dp of size m n if you're using java you can easily do this if you're using c plus plus you can declare a vector and make sure everything is initialized with minus one that that is something which we have to do to make sure that we understand that these values have been previously stored after this what is the step two store the answer that they are returning store the answer that they are returning so kindly go across and store the answer so let's store the answer over here dp of i j equal to up plus left next step three whenever there is a call please check if that answer has been previously stored or not if yes kindly return dp of ij that's how yes that's how you can easily convert a recursive solution to a memoization solution and if you have converted a recursive solution to a memorization solution the time complexity will be no more exponential rather it will be the number of states because at max you can have a call for 0 0 0 1 zero two like what calls can you have if i ask you on a very generic term you can have a call for zero zero you can have a call for zero one you can have a call for zero two zero three similarly you can have a call for one zero one one one two one 3 2 0 and so on so i can say at max you can have n cross m like what are the maximum calls of f i j you can have you can have at max of n cross m calls for recursion thereby the time complexity is this and the space complexity is still a recursion stack space which is the path length and the path length is n minus 1 plus m minus 1 that's the path length plus a big o of n cross m for the dp array that you're using so we have boiled the time complexity into much better than exponential and this will be accepted so if you are in if you are in an interview you can stop over here but i will highly recommend if you get these kind of problems go to the tabulation go to the space optimization eat as much as time as possible because if you know the problem if you can solve the problem it's better you impress the interviewer by that one problem in such a way that he'll be like wow okay but if you stop at memoration he might start asking instead of him asking you impressive all right so we have we have pretty much done the memorization form what's the next one the next one is tabulation why because we still have a recursion stack space that is being used and this somewhere might give you teal so i don't want this extreme recursion sex space to be used so i want to omit this that's where we have to think of something as tabulation so what did i teach you for tabulation if you remember whatever is the base case in recursion just write that what is the base case over here it's uh states i equal to 0 j equal to 0 return 1. so go over here first of all to declare an array of size dp of nm first of all declare an array of size dp of n and m what is the next thing that you will do is very straightforward it's you will be like declare the base case of 0 0 to be 1 okay so that's one of the things what are the other base case the other base case stated i lesser than 0 or or j less than 0 now this cannot be expressed in db so ignore this we will deal it deal with it separately so what is tabulation what is tabulation a lot of people will say tabulation is going from bottom up but do you understand the meaning of bottom up do you understand the meaning of top down that's very very important so do you understand the meaning of tabulation now a lot of people will say tabulation is bottom up and they have a tendency key bottom up means going from zero to n or something like this let's understand what is tabulation so tabulation is basically what is recursion why do we call a recursion a top down approach let's understand if you carefully observe in the recursion the call was made from here you went down you went down you went down and then you solved this base case then you accumulated the answer accumulated the answer and came back and this got its answer so you went down down down down and you got the answer and the top guy got his answer by going down there by top down the top guy got his answer by going down but in tabulation it's the opposite you start from f of 0 0 1 then you accumulate then you take this accumulate take this accumulate take this accumulate and you ultimately reach f of 2 so you start from the down which is bottom and you go to the up so you go from down down down down to up so down upper bottom up that's why tabulation is known as bottom up got it don't it's not you go from zero to one it's basically you start from the base case you accumulate you accumulate and you go and reach at the top i can and you get your answer that's why we call uh tabulation as the bottom-up approach so we have done this right what's the next thing we have to understand so we have written the base case in 2d dp it's very important to understand what are the states i'm saying the states are i j what can be the possible first value of i that you have to think you'll be like striver the first value of i will be 0 i'll be like yes but for this row 0 what can be the j value it can be 0 it can be 1 it can be 2 it can be 3 dot or dot till n minus 1 right next what can be the value of i it can be 1 for this j will be 0 1 2 dot dot n minus 1 what can be the next is value it can be 2 for this j can be 0 1 2 dot till n minus 1 so you're getting the states are like there is a state of row that's for sure there is a state for the row number which starts from 0 goes on to n minus 1 and for every row number there is a particular column number correct for every row number there is a particular column number which goes from 0 to n minus 1 correct so we know this for sure we know this for sure so just write express the states remember the step 1 to convert i'll write the steps so that it gets easy the steps to convert a memoization to a tabulation is very simple declare base case express express rather express various states in for loops or rather all states and for loops three copy the recurrence and write so step 1 is done which is declare base case step 2 express all states in for loop over here there are two states so two nested loops will go copy the recurrence let's copy the records what is the recurrence so can i say can i say i know one thing if i will be 0 and j will be 0 we have already expressed it so probably we can say if i is equal to equal to 0 and and j is equal to equal to 0 there is there is no need to do anything you can just continue or you can probably write this only the better way will be to write this only dp of zero zero will be one instead of over here you can directly write it or else if it's not the case then probably you can think of now let's let's analyze over here in the regard in the recurrence in the recurrence we see if i is equal to equal to zero j is equal to equal to zero we stop here but if it's not then what we do we go to this line which says f equal to f of i minus 1 j left is equal to f i j minus 1 correct just copy these two lines just copy these two lines okay don't think just copy up is equal to it states instead of f it will be dp i minus 1 j just write it left will be dp i comma j minus 1 so instead of f instead of parameters i express them in 2d arrays because in recursion what happened was in recursion it went down solve this then again went down solve this but over here this guy is already solved and it is stored in a dp array it is already stored in a dpi so just use those values now instead of going and calling and solving it use those values what you did after this a plus left in recursion so up plus left and where did you store it in dp of i j right that's what you do and this is how you can easily write the tabulation easy super easy isn't it so i've written the tabulation quite simply again c plus plus java doesn't matter pseudocode matters so i've written the tabulation very very easily now the question arises a straightforward question will arise but striver what if i is 0 this i minus 1 will be a problem i agree i agree so just make sure you probably can give something like if i is greater than 0 and probably something like fj is greater than 0 so then only we will take these cases otherwise not simple and if i is greater than 0 we will take it or we will take upward to be 0. like i'll show that in the code when we do the code i'll show it we can initially keep upward equal to zero left equal to zero and if if these these two cases are true then it will modify those answers and this is how you'll do it now if you remember in the recurrence we started with f of m minus 1 n minus 1 and then we split and got the answers so if m minus 1 and n minus 1 is the ultimate answer over here the ultimate answer will be stored in dp of m minus 1 and n minus 1 only thereby you get your answer that's how you do tabulation so once you've done tabulation what is the time complexity time complexity is now n into m because you're just running couple of nested loops what is the space complexity just n cross m for the space used no recursion stack space none of it that's how you get the time complexity and the space complexity right what's the next step the next step is space optimization can we do a space optimization what did i tell you in space optimization i told you striver if you see at any moment we are using the previous row we're just using the previous row and we're using previous column if there is a case of previous row and previous column then we can definitely space optimize so remember the space optimizations concept if there is a previous row and previous column we can space optimize it remember this that's the golden rule that's the golden rule yes now uh do you need this for interview the answer is no i will recommend if if you don't want to learn it you can stop over here you can stop over here there is not an it's not a necessity no space optimization just because i used to do cp i know this so well but it's not required in interviews generally the interviewers will also not be knowing space optimization so you can ignore it because they won't be rejecting you on the basis of this so you can stop the video if you don't want to learn space optimization i'll still recommend you to learn who knows the interview might be yeah understand right okay cool let's understand so what am i writing i'm specifically writing like if i write dp of ij i'm basically saying what am i using i'm using dp of the up which is j this is basically the up and the left which is basically i and j minus 1 this is the left that's what i'm using correct so when i'm starting off let's draw the matrix when i'm starting off if this is the matrix in the dp array is the for loop running the for loop is like i equal to j and j equal to j so the for loop will be like first it will go here then here then here then here then here then here then here then here then here then here here yeah yeah yeah yeah yeah yeah and so on so on so the for loop basically goes in this way and fills up the dpr in this version correct and we know this value we know this value for sure we definitely know this value which is one we go across and figure this value but for this value will there be an up for this value will there be enough no support we can keep it as zero right we can initially remember this we can initially start off with a dummy dp guy dummy dp of n size and we can initially keep it as 0 0 0 0 0 kept next we can probably say this as temporary and we can start storing it whatever value you get over here assume you get one as you may get one assuming you get one assume you get one just assume you're getting one so you store it over there correct next next this is the value that you have to compute sorry i can't read them thereby you come to the next row when you come to this pink row and when you try to compute this guy who is your up this guy is here so can i say you no more require this you no more require this you just require the value for this guy you require the value stored at here for this guy you require the value here and here for this guy this is the upward this is the left for this guy this is the upward and leftward for this guy this is the upward and left one so you just required this green so can i say i will now say this guy to be dp and this guy to be the temp and i can easily do my job once this is computed assume this is completed like 1 2 assume something like this 3 3 4 assume just i'm randomly picking up values next if you go to this guy and you're trying to compute this you'll require this guys this value and this value thereby this becomes dp so can i just store the previous row can i just store the previous row can i just store the previous row because if i'm storing the previous row whenever i'm at the current row and i'm trying to compute let's say this guy i'll require this guy and this guy this guy can easily get by row and this guy i'll easily get my previous row because in order to compute this there is no requirement of this guy there's only requirement of this up and this left thereby we can always space optimize it got it so we can always space optimize that's the proof now what i'll do is i'll try to show you how to space optimize them so the best way to space optimize is this initially you declare a dp of n initialize it with zero because initially what did you require you required this portion so dp of n declared right dpf indicate next you are trying to compute this so let's quickly write the same code without without doing uh any further stuffs let's try the same code which is j equal to 0 to n minus 1 and i know for sure if i is equal to equal to 0 and and j is equal to equal to 0 we're going to say gp of i j equal to 1 and i'm going to continue else what was i actually writing i was uh writing something as a dp of i j dp of i j right equal to dp of i minus 1 i'm not writing the cases like it might exceed but yeah i'm not writing this is what i'm writing right now let's analyze instead of dp of ij let's try to compute this particular row only yes let's try to compute this particular row only so it's a row so this is the row this is the particular row that it's computing so what i'll do is i will now say temporary of n equal to 0 and instead of this instead of this i will write temporary of j so i'm computing that particular row now over here it's the previous guy remember this it's the previous guy dpf i minus 1 means previous row and i know the previous row is dp so what i can say is i can directly go to previous row i don't need i minus 1 any further because the previous row is dp itself so i can write dp of j the previous row previous row or i can just declare it as previous right and this dp it's saying on the current row on the current row the previous column so what's the current row the current row is temporary current draw is temporary so you can be like okay i do not require i do not require to go any like dp something i can just call the temporary to get the previous so dp of j plus temporary done once remember this once you have computed this particular for loop the entire row has been computed and next the i will increase so this temporary becomes the next previous so you can just store it you can just store it right so what you'll do is when this is getting computed next when you go to the next i you make this temporary to the previous or dp whatever you can call it in this way you can easily space optimize in a 1d array yes you can easily space optimize in a 1d array it is as simple as it can get now most of you would might not have understood this i'm not sure if i was so good that you you have understood in one go just in case you did not what i'll recommend is do a dry run of the for loop by yourself throw a dry run or for loop by yourself okay and fill up and fill up you will understand everything and fill up you will understand everything why we do not require the entire grid you will understand yourself okay so as usual now let's try to code it and show all of the quotes just to have a quick revision so what did i say you're given and n right so you can say ind f int i intj and you can be like okay if i is equal to equal to zero and and j is equal to equal to zero we return zero we've done one rather so just return one to count the steps or ifs this is the case you say it's not possible to turn 0 the up will be quite simple and the left will be again quite simple which is i comma j minus 1 and you can easily return f plus left why they just check if the answer do they require uh modulated answers no so it should be fine you can say return f of what m minus 1 and n minus 1. if you just do this simply i think you should be getting an answer let's quickly run this code you see it's running fine but it'll give you a tle so it's better we just uh make sure uh to have a 2d array so in c plus plus this is how you basically declare a 2d in java people just can carry uh what to say just you can carry a 2d array that will work just carry 2d array in c plus we have to declare the sizes that's why there's a problem in carrying 2d arrays otherwise i would have done so first step is this right next step is initializing how's the next step checking if that state has been previously computed done so what i can say is let's quickly run this off should be fine okay we get some problem oh we're not passing a dp here let's really pass it okay we get a wrong answer why is that okay we have a signed mn so yeah sorry that's my bad let's do it m and n yeah working fine if we submit this so at the first time i'm submitting cool time limit exceeded so it still says our time limit exceeded probably due to the stack space that we're using so let's quickly optimize this portion and try to have it as 2d arrays ind dp of mn and i know one thing for sure the number of states will be something like i equal to zero uh i lesser than m again java people please don't cry it's the exact same same code so if your java you can also follow j this than g plus plus we know one thing if i is equal to equal to zero and j is equal to equal to zero you can be like dp of i j is equal to one else you can be like you can assign an up zero you can assign a left as a 0 if i is greater than 0 then there will always be an up which is dp of i minus 1 j if the j is greater than 0 uh the left will always be dp of i of j minus 1 at the end of the day instead of returning db of i j equal to you can say up plus left so as simple as that and what's answer where's the answer stored at guys the answer is definitely stored at return dp of m minus 1 n minus 1 so let's quickly run this off should be fine runs let's summit this let's see if we're getting at l now okay it's still giving time limit exceeded interesting the time complexity is m cross n okay fine let's optimize this let's further optimize this and let's see so what did i say how to time how to space optimizes the space optimization is quite simple we can say temporary of all the number of columns the number of columns are n you can definitely do zero so instead of temp i just make sure it's a previous dp right and over here you can definitely have vector of end of temp which is the current row that is being computed because this is the current row which is going so kindly have it as 0 right now can i say uh this is if i is equal to equal to 0 j is equal to equal to 0 you're computing the current row so the current row is now temporary understand the current row is not temporary temporary of j will be one right instead of off left let's let's uh let's try to write this instead of dp of i minus one what is i minus 1 the previous previous what is dp of i the current which is temp correct so if i name it better you probably can name it current so the current is this and that's it perfect and if once you've completed the temp yes once you've completed the temp what you can do is you can say okay fine i've completed the temp i can be like now i can just swap it i can now swap it because the current the current guy when i will increase it will become the previous so previous will be current and can i say the answer will be stored at what is this m minus 1 is previous so in previous n minus 1 the answer will be stored so if i run this it should be fine [Music] we are getting a gp was not assigned have i defined okay sorry that's my bad so dbfi means temporary or current rather so we just run this you see this running fine and if you submit this uh it will again not be running all the cases and the reason is quite simple it gives me 91 score and everything is not running the reason is i'll tell you so if you google uh the same question great unique parts the key forward channel itself you'll find a solution which is of combinatrix and the time complexity is big off the number of columns or number of rows whatever you wish to and it works in better than m into n that's why we are getting the dle i'll not teach this you can definitely watch this video again uh like this video i've already recorded so you can watch the solution over there and you can try submitting it so why did i teach the this question in complete dp because i wanted to teach you dp not how to solve this problem the concept was to teach you recursion in 2d and memoration in 2d then tabulation in 2d then space optimization in 2d and i'm very much sure that you have understood each each bit of this lecture just in case you have please please please make sure you like this video and if you're new to this channel please do consider subscribing to us it will be of immense immense help and as our tradition goes if you understood this lecture in the comment section put up a understood comment that will do me a world of good and with this let's upload this video let's read in the next [Music] then

hey everyone welcome back to the channel i hope you guys are doing extremely well so today we will be uh starting with something which is known as dp on grits or you can say dp on 2d matrix or something similar to uh which has n rows and probably not m columns but similar to that is what we will be uh starting with so to start off with we will be uh solving problems how to count paths then we will be solving problem how to count paths with obstacles then obviously we will be doing something as minimum path sum now these questions are all asked in big big tech giants okay so right after that we will be doing something like max path some but this will be under certain conditions it won&#39;t be the standard way right after that we will be doing the triangle problem and after that again we will be doing one similar problem which will be having two start points with two people just to understand how to elongate so i&#39;m very much sure after you do all these six problems because all these six problems are of different types if you have done all these six problems you can do any problem on dp on grids or on 2d matrix this is my promise to you so you just need to make sure all the six problems is what you need to watch and submit now i&#39;ll be leaving the code studio link out over there in the description you can definitely sum it over there just in case if you want any other platform you can just take up the questionnaire in the title and you can do a google search if you want any other links but but yeah i highly recommend you to try out code studio because it&#39;s a wonderful platform and something which is from india so we should definitely support it now what are the prerequisites for dp and grits i will highly recommend you to watch the lecture seven as i always say because over here i have taught you a trick where i&#39;ve told you that if you&#39;re writing a recursion function and you have to count ways how do you do that you write a base case and in that base case you either return a one or either you return a zero depending on if your conditions are met or not and then you take whatever recursions you have like how many number of recursions and then you return l plus r so if you remember these uh ways that&#39;s how you count ways and the lecture seven have deeply uh taught you this so if you don&#39;t know about this please please watch it out because without this recursion on grades or dp on grids uh will not be easy for you so please watch it before starting off with dp on grits so to start with uh let&#39;s check out the first problem which is total unique parts now what are they saying uh they&#39;re saying you&#39;re present at point a okay which is the top left cell of an m cross n matrix top left cell of an m cross n matrix your destination is point b which is the bottom right cell of the same matrix something like zero comma zero will be the top cell and the bottom will be m minus one and n minus 1 for sure your task is to find the total number of unique paths from point a to point b in other words you will be given the dimensions of the matrix as integers m and n and it asks us to find the total number of unique paths from the cell 0 0 like the point 0 0 to n minus 1 and m minus 1 for an example if i give you a matrix of 2 cross 2 size the number of unique paths will be 2. let&#39;s understand this question in deep okay so if i&#39;m saying that i&#39;m giving you a 2 cross 2 matrix okay this is the 2 cross 2 matrix definitely and over here if i&#39;m saying you you started this this is your starting point this is your ending point because if i write down it states from 0 0 to 1 comma 1 because that is the right bottom most cell so how can you basically move this okay now remember in the question it clearly states you can only move right or you can only move down no other movement is allowed only right or only down so if you move right you will end up reaching here and then again if you move right you will end up reaching here so that&#39;s one of the ways and i can see the other way is you can decide you will move here and you will reach out so i think there are a couple of unique ways unique ways in which you can reach from zero zero to one to one okay so if there are two two ways to unique ways you have to return me too so how do you do this problem now if you remember how to write recurrence that is something which i taught you how to write a recurrence that that is something which i taught you but before that we have to analyze why recursion right so what are you doing starting from something like zero comma zero and if i just write it in a generic way you&#39;re starting from zero comma zero and you&#39;re wanting to go till m minus one and n minus one that is what you are looking to do am i correct right i&#39;m absolutely correct now can i say you&#39;re basically trying out all possible ways to go from 0 0 to m minus 1 n minus 1 all possible ways now whenever you try out all possible ways what have i taught you till now all possible these means apply requisition as simple as that because if you have to count all possible ways i&#39;ll try always and i&#39;ll count them as simple as that after that dp and all that comes afterwards but if i&#39;m being asked to count always i&#39;ll try always as simple as that i&#39;ll try one way two way three way i&#39;ll keep counting in this way i can get the total number of phase right so that is what i&#39;ll do so what is the question how to write recurrence now in our one ddps i&#39;ve taught you how to write recruits what is the step one express everything in terms of indexes remember this express everything in terms of indexes but over here instead of index what will you do it&#39;s a 2d matrix so obviously indexes will be two two indexes one is the index i which will represent the row number one will be the index j will which will represent the column number so slight change in the three rules over here express everything in terms of i and j where i is basically row number j is basically column number right next explore all parts or do all stuffs whichever you call it do all stuffs the point number two stays the same if i&#39;m counting always sum up always if i&#39;m looking for max or minimal i&#39;ll take the max or minimal depending on the question if you are being asked to count all the ways you sum up all the ways if you&#39;re being asked to count max and minimal you&#39;ll count the max and minimal okay depending on your question you&#39;re going to do this so simply follow these three steps and you can write the recurrence for any 2d grid and after that you know the steps are very easy to convert a recursion to dp to rather memoration and then to tabular db and probably after that to space optimization right so let&#39;s get started so what was the question the question was stating how many ways are there in order to reach from 0 0 to n minus or rather m minus 1 n minus 1 that is the question correct so can i say let&#39;s assume i write a recursion f of i j i write a recurrence f of i j where it tells me the number of unique ways the number of unique ways in which i can reach from 0 0 to i comma j specifically what i&#39;m saying is if i&#39;m taking a grid like this and assume this is my ij i&#39;m asking in how many ways so what i&#39;m saying is in how many ways can you reach from here to here so basically i&#39;m trying to figure out the answer for this particular matrix that is what f of i j is signifying it&#39;s trying to figure out in how many ways can you reach from here to here if i and j is this right so where will we start off with we will definitely start off with f of m minus 1 and n minus 1 because this is f of n minus 1 and i want to find in how many ways can i reach from here to here so the entire matrix right so i can see i&#39;ll start off with i comma j where the initials of i comma j will be m minus 1 and n minus 1 this is generically how you determine where to start off with okay so that&#39;s what i&#39;ve done what&#39;s the first step in recursion it&#39;s the base case right so if you remember if you remember the lecture seven in lecture seven i think i&#39;ve told you how do you count ways in order to count ways you have to determine a base case that returns 1 correct so in the base case if you have reached your destination you return 1 or you return zero if you haven&#39;t reached your destination that&#39;s that&#39;s your base cases if you have reached your destination you return one if you haven&#39;t reached your destination you return zero that&#39;s what i&#39;ve taught you in the lecture seven so why don&#39;t you do that over here so what i&#39;ll say is okay i know my destination is very straightforward if i&#39;m starting from n minus one m minus one or rather the opposite m minus one and m minus one i will have to go in such a way that i reached this particular guy from here correct so i know this is the base case where i reach 0 and 0 so straight away say if i is equal to equal to 0 and j is equal to equal to 0 if that&#39;s the case i definitely know i have reached my b like the destination and if i&#39;ve reached my destination i know the recursion would have taken a path and it would have reached here so why don&#39;t i count that path so i will say return one because on returning one it gets counted lecture seven guys lecture seven of recursion series okay so that&#39;s that&#39;s how you can easily count it correct now what is the other base case assume you are standing at m minus 1 m n minus 1 there is 0 0 and you kept moving up kept moving up kept moving up kept moving up and you exceed the boundary or it might be the other way you kept moving left you kept moving left and you exceeded the boundary so you can either exceed the boundary in the upper direction which means the row number row number goes lesser than zero or the column number goes lesser than zero very straightforward so what i can say is if the row number goes lesser than zero or the column number goes lesser than zero that path is something which is not a path because it took you out of the boundary and i wanted to travel inside the matrix in order to reach from m minus 1 n minus 1 to 0 so it you got out of the boundary right so what you will do is you will say i will not count this path this path is not under my account so i will return 0 make sense that&#39;s what i&#39;ve done so the base cases have been written remember this these are the base cases that i&#39;ve written so express in terms of index and write base cases that&#39;s a step one so what i&#39;ve done is i&#39;ve made sure the step one is complete what is this explore do all stuffs now what is all stuff over here let&#39;s analyze the question stated the guy can move in the rightward direction or in the bottom word direction so if you are moving from the bottom yes if you&#39;re moving from the bottom we can say it&#39;s opposite yes we can say it&#39;s the opposite if you&#39;re moving from here to here i can so the right one will be either you can move left either you can move upward it is exactly the opposite so if it&#39;s exactly the opposite just do because there are two ways one is up one is left instead of bottom and right over here it&#39;s up and left why don&#39;t you explore it so i can say okay i have couple of ways one is the upper way where i will say okay i will move to if i go up if i go up what happens the row reduces again very basic stuff the row reduces and the column stays same if i go left what happens the rows because if i&#39;m going left we are still in the same row but we are moving a column back so thereby j minus 1 correct so we have done this and so explore all possible paths is also done what&#39;s the next step sum all the ways because you&#39;ve been asked to count the total v&#39;s so kindly sum up all the ways so why don&#39;t you sum up all the ways so what i will do is i will say return up plus left so what i&#39;ve done is i have returned up plus left so i&#39;ve summed up all the possible ways over here and this is what a recurrence will be yes this is how you can easily this is how you can easily write a recursive solution so very straight so very straightforward express explore sum up or whatever is the question stated that&#39;s how you do dp on bits so since i&#39;ve done this we have done recursion right and we know that for every index yes and for every index we are exploring uh two possible parts correct so i can say the time complexity of recursion how many ways are there like how many boxes are there in the matrix m into n boxes and for every box you&#39;re taking two two parts up left up left up left up left so if for every boxes you&#39;re taking two parts can i say can i say all the boxes in total yes all the boxes in total will be having 2 into 2 into 2 into 2 into 2 into 2 parts which is 2 into m into n parts so the time complexity is this which is exponential in nature right space complexity is a recursive stack space which will be uh the path length which will be the path length remember the space complexity will be the path length why because if you&#39;re wanting to reach here let&#39;s say from 3 comma 3 the path length will be you will go to two comma two then you will uh sorry or two comma three rather then it will go to one comma three then it will go to zero comma three then it&#39;ll go to zero comma two then you&#39;ll go to zero comma one and then you&#39;ll go to this so the path length contains one length two length three length four length five length six length so it&#39;s basically the path length is nothing but m minus one plus n minus one is the path length because over here you took if you see carefully over here if the length was four you ended up taking three upward directions and you ended up taking three leftward directions right thereby the path length is uh this so this is the recursions time complexity and the stack space complexity now what&#39;s the next step what&#39;s the next step in recursion i have told you easily how do you optimize recursion in order to optimize recursion what you generally do is you try to convert that into a possible dp solution correct and how do you do this in order to do this you try to do something which is known as memo i action correct but when can you apply memorization if there are overlapping sub problems yes if there are overlapping sub problems you tend to apply something like a memo iration so why don&#39;t we do that so what i&#39;ll do is i will take m equal to uh let&#39;s say three i&#39;ll take n equal to three and i&#39;ll try to figure out how many total ways are there correct so practically speaking this is how the grid will look and you want to find how many ways are there to reach from this particular position to this particular position right so let&#39;s do that so this is 0 1 2 this is again 0 1 2 so we start with f of two comma two correct now where can f of two comma two go it can either go to the upward direction which is definitely f of the row numbers reduces by one and the column stays the same or it goes to the leftward direction when the row number stays same and the column number reduces by one correct and if you know in recursion if this is the upper direction this is the leftward direction which recursion will be occurring first obviously this recurrence will be occurring first so let&#39;s do this recurrence now f of one two where can it go it can definitely go to something as f of zero two and it can definitely go to something as f of one comma one this is the upward direction this is the left direction this is the up this is the left now where can f of zero to go it can again go to the up so if it goes to the up it&#39;s minus one comma two and if it goes to the left it&#39;s basically zero comma one correct so what happens over here whenever you reach f of minus one comma two what happens over here so if you remember the moment the row goes lesser than zero there was a base cases i lesser than zero or or j lesser than zero if any of these things happen you end up returning a zero so you end up returning a zero over correct over here there is something like f of zero one again it can go up which is minus one comma one or it can go to the left which is zero comma zero correct so minus one comma one will again is the upward direction which will return zero and this guy ends up returning one because this is where your destination is because this is where your destination is you have reached f of zero comma zero so that thereby this is your destination so how will the recursion be like f of zero comma one would have called up would have called left so the up would have been minus one comma one and the left would have been f zero comma zero this guy gets one this guy gets zero and in order you return the summation of both which is zero plus one thereby this guy gets a value of one so i can say this guy gets a value of one so you can easily return that value one correct so thereby thereby let&#39;s quickly erase this and try to solve this recursion now here at f of zero two at f of zero to what would have happened it would have gone to up which is f minus one two which gave him zero which gave him zero it have gone to left which would have give uh gave him f of zero one which is one so thereby it returns 0 plus 1 makes it a value of 1 so it returns a 1. so let&#39;s quickly raise it so this is how it will be and in the next step yes in the next step what happens there is something like f of one two it goes up and now it goes left so f of one one will be something like f of zero one because it has to go up and similarly it will be like i have to go left which will be f 1 0 correct so if you carefully see we get our first sub problem 0 1 has been solved here so there is no need to go further down into f of minus 1 1 which is the top and there is no need to go to the left so i got my first sub problem thereby i see there are overlapping sub problems and if there are overlapping sub problems what can we apply we can definitely apply memoization and what is the shortest what is the shortest trick that i have told you to apply memoration just figure out which is the changing parameters so there are a couple of parameters correct one parameter was i the other parameter was j so if there was a parameter i which is changing there is a parameter j which is changing so what is the i&#39;s maximum value i can say it&#39;s m minus 1 because that is where we start the recursion call what is the g is maximum value n minus 1 because that is where we start the recursion call so i can say if i require the index m minus 1 i will have to declare an array of size m because if i declare an array of size m i will get the index m minus 1. similarly similarly in order to get an index n minus 1 i have to declare an array of size n so basically i can say i will be requiring a dp of m cross n which is a 2d dp of m cross n so if i have a 2d dp i can convert this into a memo iodization solution so how do you convert this into a membranation solution again very straightforward step one declare the dp declare the dp of size m n if you&#39;re using java you can easily do this if you&#39;re using c plus plus you can declare a vector and make sure everything is initialized with minus one that that is something which we have to do to make sure that we understand that these values have been previously stored after this what is the step two store the answer that they are returning store the answer that they are returning so kindly go across and store the answer so let&#39;s store the answer over here dp of i j equal to up plus left next step three whenever there is a call please check if that answer has been previously stored or not if yes kindly return dp of ij that&#39;s how yes that&#39;s how you can easily convert a recursive solution to a memoization solution and if you have converted a recursive solution to a memorization solution the time complexity will be no more exponential rather it will be the number of states because at max you can have a call for 0 0 0 1 zero two like what calls can you have if i ask you on a very generic term you can have a call for zero zero you can have a call for zero one you can have a call for zero two zero three similarly you can have a call for one zero one one one two one 3 2 0 and so on so i can say at max you can have n cross m like what are the maximum calls of f i j you can have you can have at max of n cross m calls for recursion thereby the time complexity is this and the space complexity is still a recursion stack space which is the path length and the path length is n minus 1 plus m minus 1 that&#39;s the path length plus a big o of n cross m for the dp array that you&#39;re using so we have boiled the time complexity into much better than exponential and this will be accepted so if you are in if you are in an interview you can stop over here but i will highly recommend if you get these kind of problems go to the tabulation go to the space optimization eat as much as time as possible because if you know the problem if you can solve the problem it&#39;s better you impress the interviewer by that one problem in such a way that he&#39;ll be like wow okay but if you stop at memoration he might start asking instead of him asking you impressive all right so we have we have pretty much done the memorization form what&#39;s the next one the next one is tabulation why because we still have a recursion stack space that is being used and this somewhere might give you teal so i don&#39;t want this extreme recursion sex space to be used so i want to omit this that&#39;s where we have to think of something as tabulation so what did i teach you for tabulation if you remember whatever is the base case in recursion just write that what is the base case over here it&#39;s uh states i equal to 0 j equal to 0 return 1. so go over here first of all to declare an array of size dp of nm first of all declare an array of size dp of n and m what is the next thing that you will do is very straightforward it&#39;s you will be like declare the base case of 0 0 to be 1 okay so that&#39;s one of the things what are the other base case the other base case stated i lesser than 0 or or j less than 0 now this cannot be expressed in db so ignore this we will deal it deal with it separately so what is tabulation what is tabulation a lot of people will say tabulation is going from bottom up but do you understand the meaning of bottom up do you understand the meaning of top down that&#39;s very very important so do you understand the meaning of tabulation now a lot of people will say tabulation is bottom up and they have a tendency key bottom up means going from zero to n or something like this let&#39;s understand what is tabulation so tabulation is basically what is recursion why do we call a recursion a top down approach let&#39;s understand if you carefully observe in the recursion the call was made from here you went down you went down you went down and then you solved this base case then you accumulated the answer accumulated the answer and came back and this got its answer so you went down down down down and you got the answer and the top guy got his answer by going down there by top down the top guy got his answer by going down but in tabulation it&#39;s the opposite you start from f of 0 0 1 then you accumulate then you take this accumulate take this accumulate take this accumulate and you ultimately reach f of 2 so you start from the down which is bottom and you go to the up so you go from down down down down to up so down upper bottom up that&#39;s why tabulation is known as bottom up got it don&#39;t it&#39;s not you go from zero to one it&#39;s basically you start from the base case you accumulate you accumulate and you go and reach at the top i can and you get your answer that&#39;s why we call uh tabulation as the bottom-up approach so we have done this right what&#39;s the next thing we have to understand so we have written the base case in 2d dp it&#39;s very important to understand what are the states i&#39;m saying the states are i j what can be the possible first value of i that you have to think you&#39;ll be like striver the first value of i will be 0 i&#39;ll be like yes but for this row 0 what can be the j value it can be 0 it can be 1 it can be 2 it can be 3 dot or dot till n minus 1 right next what can be the value of i it can be 1 for this j will be 0 1 2 dot dot n minus 1 what can be the next is value it can be 2 for this j can be 0 1 2 dot till n minus 1 so you&#39;re getting the states are like there is a state of row that&#39;s for sure there is a state for the row number which starts from 0 goes on to n minus 1 and for every row number there is a particular column number correct for every row number there is a particular column number which goes from 0 to n minus 1 correct so we know this for sure we know this for sure so just write express the states remember the step 1 to convert i&#39;ll write the steps so that it gets easy the steps to convert a memoization to a tabulation is very simple declare base case express express rather express various states in for loops or rather all states and for loops three copy the recurrence and write so step 1 is done which is declare base case step 2 express all states in for loop over here there are two states so two nested loops will go copy the recurrence let&#39;s copy the records what is the recurrence so can i say can i say i know one thing if i will be 0 and j will be 0 we have already expressed it so probably we can say if i is equal to equal to 0 and and j is equal to equal to 0 there is there is no need to do anything you can just continue or you can probably write this only the better way will be to write this only dp of zero zero will be one instead of over here you can directly write it or else if it&#39;s not the case then probably you can think of now let&#39;s let&#39;s analyze over here in the regard in the recurrence in the recurrence we see if i is equal to equal to zero j is equal to equal to zero we stop here but if it&#39;s not then what we do we go to this line which says f equal to f of i minus 1 j left is equal to f i j minus 1 correct just copy these two lines just copy these two lines okay don&#39;t think just copy up is equal to it states instead of f it will be dp i minus 1 j just write it left will be dp i comma j minus 1 so instead of f instead of parameters i express them in 2d arrays because in recursion what happened was in recursion it went down solve this then again went down solve this but over here this guy is already solved and it is stored in a dp array it is already stored in a dpi so just use those values now instead of going and calling and solving it use those values what you did after this a plus left in recursion so up plus left and where did you store it in dp of i j right that&#39;s what you do and this is how you can easily write the tabulation easy super easy isn&#39;t it so i&#39;ve written the tabulation quite simply again c plus plus java doesn&#39;t matter pseudocode matters so i&#39;ve written the tabulation very very easily now the question arises a straightforward question will arise but striver what if i is 0 this i minus 1 will be a problem i agree i agree so just make sure you probably can give something like if i is greater than 0 and probably something like fj is greater than 0 so then only we will take these cases otherwise not simple and if i is greater than 0 we will take it or we will take upward to be 0. like i&#39;ll show that in the code when we do the code i&#39;ll show it we can initially keep upward equal to zero left equal to zero and if if these these two cases are true then it will modify those answers and this is how you&#39;ll do it now if you remember in the recurrence we started with f of m minus 1 n minus 1 and then we split and got the answers so if m minus 1 and n minus 1 is the ultimate answer over here the ultimate answer will be stored in dp of m minus 1 and n minus 1 only thereby you get your answer that&#39;s how you do tabulation so once you&#39;ve done tabulation what is the time complexity time complexity is now n into m because you&#39;re just running couple of nested loops what is the space complexity just n cross m for the space used no recursion stack space none of it that&#39;s how you get the time complexity and the space complexity right what&#39;s the next step the next step is space optimization can we do a space optimization what did i tell you in space optimization i told you striver if you see at any moment we are using the previous row we&#39;re just using the previous row and we&#39;re using previous column if there is a case of previous row and previous column then we can definitely space optimize so remember the space optimizations concept if there is a previous row and previous column we can space optimize it remember this that&#39;s the golden rule that&#39;s the golden rule yes now uh do you need this for interview the answer is no i will recommend if if you don&#39;t want to learn it you can stop over here you can stop over here there is not an it&#39;s not a necessity no space optimization just because i used to do cp i know this so well but it&#39;s not required in interviews generally the interviewers will also not be knowing space optimization so you can ignore it because they won&#39;t be rejecting you on the basis of this so you can stop the video if you don&#39;t want to learn space optimization i&#39;ll still recommend you to learn who knows the interview might be yeah understand right okay cool let&#39;s understand so what am i writing i&#39;m specifically writing like if i write dp of ij i&#39;m basically saying what am i using i&#39;m using dp of the up which is j this is basically the up and the left which is basically i and j minus 1 this is the left that&#39;s what i&#39;m using correct so when i&#39;m starting off let&#39;s draw the matrix when i&#39;m starting off if this is the matrix in the dp array is the for loop running the for loop is like i equal to j and j equal to j so the for loop will be like first it will go here then here then here then here then here then here then here then here then here then here here yeah yeah yeah yeah yeah yeah and so on so on so the for loop basically goes in this way and fills up the dpr in this version correct and we know this value we know this value for sure we definitely know this value which is one we go across and figure this value but for this value will there be an up for this value will there be enough no support we can keep it as zero right we can initially remember this we can initially start off with a dummy dp guy dummy dp of n size and we can initially keep it as 0 0 0 0 0 kept next we can probably say this as temporary and we can start storing it whatever value you get over here assume you get one as you may get one assuming you get one assume you get one just assume you&#39;re getting one so you store it over there correct next next this is the value that you have to compute sorry i can&#39;t read them thereby you come to the next row when you come to this pink row and when you try to compute this guy who is your up this guy is here so can i say you no more require this you no more require this you just require the value for this guy you require the value stored at here for this guy you require the value here and here for this guy this is the upward this is the left for this guy this is the upward and leftward for this guy this is the upward and left one so you just required this green so can i say i will now say this guy to be dp and this guy to be the temp and i can easily do my job once this is computed assume this is completed like 1 2 assume something like this 3 3 4 assume just i&#39;m randomly picking up values next if you go to this guy and you&#39;re trying to compute this you&#39;ll require this guys this value and this value thereby this becomes dp so can i just store the previous row can i just store the previous row can i just store the previous row because if i&#39;m storing the previous row whenever i&#39;m at the current row and i&#39;m trying to compute let&#39;s say this guy i&#39;ll require this guy and this guy this guy can easily get by row and this guy i&#39;ll easily get my previous row because in order to compute this there is no requirement of this guy there&#39;s only requirement of this up and this left thereby we can always space optimize it got it so we can always space optimize that&#39;s the proof now what i&#39;ll do is i&#39;ll try to show you how to space optimize them so the best way to space optimize is this initially you declare a dp of n initialize it with zero because initially what did you require you required this portion so dp of n declared right dpf indicate next you are trying to compute this so let&#39;s quickly write the same code without without doing uh any further stuffs let&#39;s try the same code which is j equal to 0 to n minus 1 and i know for sure if i is equal to equal to 0 and and j is equal to equal to 0 we&#39;re going to say gp of i j equal to 1 and i&#39;m going to continue else what was i actually writing i was uh writing something as a dp of i j dp of i j right equal to dp of i minus 1 i&#39;m not writing the cases like it might exceed but yeah i&#39;m not writing this is what i&#39;m writing right now let&#39;s analyze instead of dp of ij let&#39;s try to compute this particular row only yes let&#39;s try to compute this particular row only so it&#39;s a row so this is the row this is the particular row that it&#39;s computing so what i&#39;ll do is i will now say temporary of n equal to 0 and instead of this instead of this i will write temporary of j so i&#39;m computing that particular row now over here it&#39;s the previous guy remember this it&#39;s the previous guy dpf i minus 1 means previous row and i know the previous row is dp so what i can say is i can directly go to previous row i don&#39;t need i minus 1 any further because the previous row is dp itself so i can write dp of j the previous row previous row or i can just declare it as previous right and this dp it&#39;s saying on the current row on the current row the previous column so what&#39;s the current row the current row is temporary current draw is temporary so you can be like okay i do not require i do not require to go any like dp something i can just call the temporary to get the previous so dp of j plus temporary done once remember this once you have computed this particular for loop the entire row has been computed and next the i will increase so this temporary becomes the next previous so you can just store it you can just store it right so what you&#39;ll do is when this is getting computed next when you go to the next i you make this temporary to the previous or dp whatever you can call it in this way you can easily space optimize in a 1d array yes you can easily space optimize in a 1d array it is as simple as it can get now most of you would might not have understood this i&#39;m not sure if i was so good that you you have understood in one go just in case you did not what i&#39;ll recommend is do a dry run of the for loop by yourself throw a dry run or for loop by yourself okay and fill up and fill up you will understand everything and fill up you will understand everything why we do not require the entire grid you will understand yourself okay so as usual now let&#39;s try to code it and show all of the quotes just to have a quick revision so what did i say you&#39;re given and n right so you can say ind f int i intj and you can be like okay if i is equal to equal to zero and and j is equal to equal to zero we return zero we&#39;ve done one rather so just return one to count the steps or ifs this is the case you say it&#39;s not possible to turn 0 the up will be quite simple and the left will be again quite simple which is i comma j minus 1 and you can easily return f plus left why they just check if the answer do they require uh modulated answers no so it should be fine you can say return f of what m minus 1 and n minus 1. if you just do this simply i think you should be getting an answer let&#39;s quickly run this code you see it&#39;s running fine but it&#39;ll give you a tle so it&#39;s better we just uh make sure uh to have a 2d array so in c plus plus this is how you basically declare a 2d in java people just can carry uh what to say just you can carry a 2d array that will work just carry 2d array in c plus we have to declare the sizes that&#39;s why there&#39;s a problem in carrying 2d arrays otherwise i would have done so first step is this right next step is initializing how&#39;s the next step checking if that state has been previously computed done so what i can say is let&#39;s quickly run this off should be fine okay we get some problem oh we&#39;re not passing a dp here let&#39;s really pass it okay we get a wrong answer why is that okay we have a signed mn so yeah sorry that&#39;s my bad let&#39;s do it m and n yeah working fine if we submit this so at the first time i&#39;m submitting cool time limit exceeded so it still says our time limit exceeded probably due to the stack space that we&#39;re using so let&#39;s quickly optimize this portion and try to have it as 2d arrays ind dp of mn and i know one thing for sure the number of states will be something like i equal to zero uh i lesser than m again java people please don&#39;t cry it&#39;s the exact same same code so if your java you can also follow j this than g plus plus we know one thing if i is equal to equal to zero and j is equal to equal to zero you can be like dp of i j is equal to one else you can be like you can assign an up zero you can assign a left as a 0 if i is greater than 0 then there will always be an up which is dp of i minus 1 j if the j is greater than 0 uh the left will always be dp of i of j minus 1 at the end of the day instead of returning db of i j equal to you can say up plus left so as simple as that and what&#39;s answer where&#39;s the answer stored at guys the answer is definitely stored at return dp of m minus 1 n minus 1 so let&#39;s quickly run this off should be fine runs let&#39;s summit this let&#39;s see if we&#39;re getting at l now okay it&#39;s still giving time limit exceeded interesting the time complexity is m cross n okay fine let&#39;s optimize this let&#39;s further optimize this and let&#39;s see so what did i say how to time how to space optimizes the space optimization is quite simple we can say temporary of all the number of columns the number of columns are n you can definitely do zero so instead of temp i just make sure it&#39;s a previous dp right and over here you can definitely have vector of end of temp which is the current row that is being computed because this is the current row which is going so kindly have it as 0 right now can i say uh this is if i is equal to equal to 0 j is equal to equal to 0 you&#39;re computing the current row so the current row is now temporary understand the current row is not temporary temporary of j will be one right instead of off left let&#39;s let&#39;s uh let&#39;s try to write this instead of dp of i minus one what is i minus 1 the previous previous what is dp of i the current which is temp correct so if i name it better you probably can name it current so the current is this and that&#39;s it perfect and if once you&#39;ve completed the temp yes once you&#39;ve completed the temp what you can do is you can say okay fine i&#39;ve completed the temp i can be like now i can just swap it i can now swap it because the current the current guy when i will increase it will become the previous so previous will be current and can i say the answer will be stored at what is this m minus 1 is previous so in previous n minus 1 the answer will be stored so if i run this it should be fine [Music] we are getting a gp was not assigned have i defined okay sorry that&#39;s my bad so dbfi means temporary or current rather so we just run this you see this running fine and if you submit this uh it will again not be running all the cases and the reason is quite simple it gives me 91 score and everything is not running the reason is i&#39;ll tell you so if you google uh the same question great unique parts the key forward channel itself you&#39;ll find a solution which is of combinatrix and the time complexity is big off the number of columns or number of rows whatever you wish to and it works in better than m into n that&#39;s why we are getting the dle i&#39;ll not teach this you can definitely watch this video again uh like this video i&#39;ve already recorded so you can watch the solution over there and you can try submitting it so why did i teach the this question in complete dp because i wanted to teach you dp not how to solve this problem the concept was to teach you recursion in 2d and memoration in 2d then tabulation in 2d then space optimization in 2d and i&#39;m very much sure that you have understood each each bit of this lecture just in case you have please please please make sure you like this video and if you&#39;re new to this channel please do consider subscribing to us it will be of immense immense help and as our tradition goes if you understood this lecture in the comment section put up a understood comment that will do me a world of good and with this let&#39;s upload this video let&#39;s read in the next [Music] then

Transcript for:Lecture on Dynamic Programming on Grids

Transcript for:
Lecture on Dynamic Programming on Grids