se is continue. That means we would just continue to the next iteration of the loop. We would just skip this coordinate. But you can see it's not as simple as just taking a row and a column. I'm writing it this way, basically to eliminate duplicate code, we could have conditional, we could basically have this conditional four times for all four directions, or we could put this in a helper function. Another way to do it, though, is to take all four of the neighbors. When we say neighbors, these are not actually the neighbors necessarily. These are basically the directions one. So this would represent the right direction. This would represent the left direction. This would represent below and this would represent above. So when we take these directions and add them to the row and the column, so that's what you can see we're doing for basically all of these for row. We're adding D R D R just stands for difference in row. We're basically saying how much did the row change? How much is the difference of the row? This is zero. And that means the column is changing, right? Basically, what I'm saying is by taking these, which represent the difference in row and the difference in column and adding them to the row and the column, we will basically have all four directions enumerated. So this is sort of more complicated than it looks. You can write it out the long way if you would like, or you can even, you know, put this kind of stuff in a helper function if you would like, but this is another common way that it's done. And this sort of minimizes the amount of code that we have to write. I could also here have declared another variable saying, you know, the new row and the new column so that we wouldn't have had that right row plus D R C plus DC out, you know, multiple times, you can see I had to write that out a few times here, but I wanted to make it explicit in this case to show you exactly what we're doing. But feel free to modify this to make it look more simple or match your coding style, however you would like. But now that we kind of covered what this is doing, this is just a bunch of boilerplate to go through all four directions using a loop. What are we actually going to do with those four directions? Well, of course, we know that the base case, we go out of bounds, reach the same position twice, or we reach a block position. That's when we do nothing, we continue. Otherwise, it means we reached a valid position. By the way, which one of these four is a valid position, only the one to the right over here. So this is the only valid position. What are we going to do with this? We're now going to add it to our queue. We know that's the next layer. This is the only node we can reach with a path length of one. So we add it to the queue and we also add it to visit, we don't want to visit this multiple times now. Now after we've gone through all the neighbors, and we popped this position from our queue. Now we have this in our queue, and we popped this from our queue. Now we have this in our queue. So after that loop, we're also going to increment the length by one to indicate that this layer that we have now added to our queue can be reached, all these nodes can be reached with a path length of one. So now let's continue. And at this point, I'm going to focus mostly on the visuals. We know we can go in four directions down up can't go the in either of those directions, we can't go left, it's already been visited, but we can go to the right. And that's the only position we can go to. That's the only thing we're going to end up adding to our queue and adding to visit. And of course, this is going to have been popped from the queue. And after that's done, our length is going to be incremented to two. By the way, when we did pop this guy, we checked. Is it the destination? It was not. So we did not return the length, which at the time when we popped this was one. So if it was the destination, we would have returned one, which is what we would have wanted to do. So now we get to a bit of a more interesting case. We only have one value again in our queue, but we have two valid directions we can go to right and below. And both of those are going to be added to the queue and added to the visit hash set. We wouldn't be able to add this one, of course, because it's already been added to the visit hash set. And then we would increment our length by one. So our length would now be three. So our length would now be three. I'm going to write the length below now since we're kind of running out of space up there. But basically, this is the layer of nodes that we can reach with a path length of three starting from the top left. And through that process, we know we would have popped this from our queue. So this is now part of our queue. We're going to go to the next layer. So this is where it's going to get a bit interesting because the length of our queue is actually two now. So we're going to pop both of these from our queue. It doesn't really matter which one we pop first. Let's just say we popped this guy first. So we pop it from the queue and we get its neighbors. Can't go up. It's already been visited. Can't go left. It's blocked. We can go to the right and we can go below. So what we're going to do is add these to our queue and add them to the visit hash set. Now you're going to see why we add to the visit hash set as soon as we add to the queue because that's very important because next we're going to pop this guy from our queue. So we pop this from the queue and we see can we go up? Nope. Can we go to the left? Nope. Can't go to the right. And we can't even go below. This was open, but we added it to the visit hash set. So now it's we know it's already been added to the queue. So we're not going to add it to the queue again. This is very important. This is why the algorithm runs an end times M complexity because we know for sure we're never going to add the same position to the queue twice. We're never going to visit the same position twice. And we still know that these are all of the cells we can reach with a path length of four. So this is going layer by layer. That's very important. So now we have two positions in our queue. So we're going to execute this loop again twice for two iterations. We're going to pop let's say this guy first.  So we pop it, but we don't end up adding anything through our queue. It's just going to execute the continue statement. So at this point our queue only has this guy. So we pop this from our queue and then we add its neighbors can't go up can't go right. We can go below and we can go to the left. So these are now going to be added to our queue. What's the length to reach these? Well previously it was four. So let's add one and get five. We can reach both of these with a length of five. That's the shortest path to reach both of them. Now we don't actually know what is the shortest path. We're not keeping track of that. It would probably be this or this. But that's not important. We just care about the length in this case. And at this point we're almost done. We have two positions in our queue pop this guy can't go up. It's blocked can't go to the right. It's visited can't go below its blocked. We can go to the left and add this to our queue and to our visit asset.  We can only go to the right. And at this point we've gotten to the destination. But you can see this is where we look for the destination after we pop from our queue is when we check is this the destination. We don't check if it's the destination when we're adding to the queue. I mean we could have done it this way we would have to rewrite it a little bit because we're only incrementing the length after we've updated the entire queue. But let's just run this very quickly. So we finished the this layer. So now our green layer here takes a length of six to reach now finishing up let's say we pop this guy first we pop it and we can't go up can't go left can't go right we just add this guy to our queue and then we pop this one. So when we pop it we check is it the result that we're looking for it is. And by the way at this point our length would still be six. So we would return that and that would be the result. So I color coded it a bit to indicate to you the length of each of these. So to actually run that you could see BFS would just be past the grid and then the function itself would take care of the rest and then we could print the result in this case it would be six the path would look something like this. But that's the main idea as you can see with this approach we're never going to visit the same position twice we're never going to add the same position to the queue twice worst case we'd visit the entire grid so in that case the time complexity would be the dimensions of the grid which is n times m the space complexity would be the same because that's the max size that our visit hash set or our queue could end up being so this would be the memory complexity and also the time complexity. So in my opinion this is a bit more easy to understand in terms of like the visuals code wise there's a lot of boiler plate though as you can see so it can kind of be a pain to write out but once you get used to it it's just a matter of writing out all the you know edge cases and getting them right but it can definitely take a while to get good at it. I'd recommend taking a look at some of the problems in the practice section under the graph topic because bfs is definitely a common algorithm that comes up a lot. Next let's move on to adjacency lists and the good thing in my opinion is that these are much more simple to run an algorithm on rather than on a matrix. Now originally we talked about the idea of having a graph node class or an object for an adjacency list where you know we're storing some kind of value it could be a string a character an integer and then it's also going to have a list of neighbors the neighbors are going to be pointers they could be directed or undirected but essentially they're going to be pointers pointing at other nodes that's one way to do it and if we were actually creating our own graph we would do something like that but when it comes to coding interviews it's actually much more common to just use a hash map to represent an adjacency list because as you can see there's two things we care about the value or you know the id of each node as long as that is unique and for coding interviews it's almost always unique each graph will have something that uniquely identifies it whether it's an integer or a character or a string in this case let's say we have a character a and so that's going to be the key of our hash map so this is how i'm doing it in python but the important thing here is that this is the key the character is the key and the value for that key is going to be a list and that list is going to represent the neighbors so this is just an example adjacency list where we have two nodes a and b now the lists here are empty so that basically means there aren't any pointers that's just a very simple example just to kind of show you that this same idea can be represented using a hash map now let's actually do a very common algorithm when it comes to coding interviews which is usually you're not just given the adjacency list itself you have to build it yourself you are given enough information to build it though so the most common thing is you're given a list of edges in this case these are directed edges and we want to build an adjacency list with them what does directed mean again well for this edge we're basically saying that there exists some edge going from a to b so it's directed so it's going from a to b this is what it would look like in terms of the picture now how do now how do we go about actually building the adjacency list well let's just first declare a variable this is let's say an empty hash map we're going through every single edge which is a pair of nodes here the values are you know the identifiers for that node so we're calling it in this case source destination so source is going to be the first of the pair and the destination is going to be the second of the pair this is how you would do it in python but other languages will also be provided below so one thing is that our hash map is empty so these keys might not even be in the hash map itself so we so if they're not that's what we want to do so we're first going to check is source not in the adjacency list is this key not in the hash map if it's not let's add it to the hash map and give it a value of an empty array so the neighbors are you know initially empty we just added this node to the adjacency list we're going to do the same thing with the destination even though we're not going to be adding anything to the array of the destination neighbors because we want to at the very least make sure that every node that we saw in the list of edges is added to the adjacency list even if it doesn't have any neighbors because we want to at least have an empty list to you know confirm it doesn't have any neighbors so here what we would say is for the adjacency list of the source for our first example that would be a we're going to append to its neighbors which initially is an empty list we're going to append b so visually we would say a points at b it has a neighbor b going to the second edge we would do the same thing b though in this case has already been added to the adjacency list we did that previously with this line but c is not so we add c to the adjacency list it doesn't have any neighbors though of course just yet at least but now we know b points at c so we have an edge going from b to c and then third edge b to e we're going to do the same thing put an edge over here c to e that means there's an edge going like this and e to d so there is an edge going like this so this is what the graph would look like we were given all the information we needed we were given the edges but from the edges we could imply what the nodes are and then we have a representation that looks like this this is the same information that would be stored in our adjacency list which you know we're using a hash map to do that and you can see why because it gives us all we really need now let's move on to actually running some common algorithms like dfs and bfs on adjacency lists and the good thing is these are a little bit easier than doing them on a matrix so let's run pretty much the same algorithm we did on the matrix using dfs depth first search we want to count all the paths and again this is going to be a backtracking algorithm but the code is a lot more simple mostly because we don't have a thousand edge cases to worry about we don't have to worry about going out of bounds that's what makes adjacency lists nice so assuming we're given this input that's our adjacency list and assuming it was given in the form of a hash map in python we're going to run dfs find account the paths let's say the node the starting node is going to be a in our dfs and the target node is going to be e so we want to count the paths from a to e the adjacency list is passed in and we also have a hash set which is going to keep track of visited nodes along a single path just like we did with a matrix so that hash set is passed in we're going to call this function and then print whatever it returns so starting at a we check has this node already been visited if it has there's zero paths from here to the result it's not the case though well is this node already the target if it is then that means we found a path to the target we can return one it's not e so it's not the target then we declare a variable to count how many paths from a to e we add the node to the visit hash set and we go through its list of neighbors the good thing here is it's so easy to iterate through the list of neighbors because we have it in our adjacency list we don't have to go you know manually in four different directions that's really annoying to write out so we call dfs on each of the neighbor nodes now maybe a doesn't even have any neighbors you know that would be an empty list an empty array and then this for loop would never even execute but in this case a does have one neighbor so we were at a now we're going to be at b i'm using these arrows to kind of indicate which node that we've already visited and which node we're currently at so we're at b right now so recursively we're at b is this node already been visited nope is this node the target nope so now we're counting how many paths from b to e so that will be zero initially we'll add b to the visit hash set and go through the neighbors of b it actually has two neighbors c and e let's say we call dfs on c first notice how it's dfs not bfs that means we're going as deep as we can in one direction so we get to see this is not visited already and it's not the target so we count paths from c to the target and we add c to visit hash set and we go through its list of neighbors it only has a single neighbor so then we call dfs on e now we are at e it's not been visited already but it is the target node so we return one in this case that means we found this path that leads to e so we return one this is the base case so we return one we backtrack and then we end up back at c from c we called dfs on e it returned one we add one to our count and then this loop is going to stop because we only had one neighbor from c so then we're going to backtrack now from visit we're going to remove c so you can think of that as you know removing this pointer and then we're going to return the count which is one and that one is going to be returned back to b and then from b's perspective we're going to take that result one add it to its count so its count is now one but for b it actually has a second neighbor it has the neighbor e so we're going to call dfs now on e from b so pointer here again same base case is going to execute now we found another path that looks like this so we return one from e we add that one to our count for b which is two so we know there's two paths from b to e and then that's its own and that's its last neighbor so then we're going to remove b from the visit so you can think of that as removing this pointer and that's kind of the backtracking part and then two is going to be returned back up to a so two is over here and then a only had a single neighbor so its loop is going to stop and it's going to end up returning to so there were two paths from a to e now we didn't even end up visiting d that's because we didn't need to whenever we get to the target we are going to immediately stop so you can see that this is much more simple than running it on a matrix but the core ideas are definitely the same we have some base cases we want to you know enumerate every single possible path and if we end up visiting a node then we want to stop now in this case we never visited the same node twice along a single path but for example suppose that from c there was actually a pointer back to b in that case uh you know let's say we do a dfs we get to a then we get to b then we get to c and then from c we have two choices we can go to e or we can go back to b but if we did that we went back to b we'd see well we've already visited this once along this path so we can't just visit it again so at that point we would end up returning zero from there we'd say that there's zero paths going to the target where we start at b come to c and then go back to b there's zero valid paths doing it like that so it can get complicated to analyze the time complexity of this type of brute force back tracking dfs approach so i'll try to keep it simple we know that any given path we know that we're going to go through every single possible path in the entire graph i mean we have to to count the paths so that could be the worst case the length of a path is going to be no larger than the number of vertices that we have because we can only visit each vertices once along a given path so that is going to kind of represent the height of our decision tree now for each a vertex how many choices could we have in the worst case it would be you know every vertex is connected to every other vertex so that would mean v choices but we're going to say let's just use some value n where n is the average number of edges that each node has this is a slightly more common way of talking about it but the important thing is just kind of understanding the ideas that i'm talking about here understanding the ideas of choices and how long could a path be and stuff like that so the height again of this decision tree when i say decision tree i mean you know all the decisions that we could make when we're counting the paths on this graph the height is going to be v the number of choices we could make is going to be n where n is let's say the average number of edges that each vertex has so in that case the time complexity analyzing this the same way that we did a binary tree is going to be something like n to the power of v so big o of n to the power of v now it's pretty rare to actually have to analyze the time complexity this type of way but the important thing to recognize here is that this dfs this backtracking is not going to be very efficient just like most backtracking algorithms this is exponential we know it's exponential because the power here is going to be a variable if we had n squared that's not the end of the world because the power is a constant value even n cubed wouldn't be that bad but here as the size of our graph grows which is the this time complexity is going to grow extremely quickly so this is very very inefficient bfs is much more efficient as we will see so let's take a look at the same example problem let's try to find the shortest path from a node to a target so in this case the starting is going to be a again and the target is going to be e those are the parameters we're passing it and we're passing in the adjacency list that we built you know for this representation now the bfs is going to work similar to the matrix we're going to initialize a few variables the length is initially going to be zero we're going to have a hash set and we're going to add the starting node as visited to that hash set and we're going to have a q and we're going to add that starting node to the q so that's the first level in our bfs so while our q is not empty we have a single node in our q right now we're going to iterate through the length of that q at that given moment so we're going to take a snapshot of the length it's one so we're going to run this loop one time and we're going to pop one node so we pop that node this is our current we're going to check is it equal to the target if it is we can return the length which is initially zero so we're saying you know the length from starting here to arriving here is zero that would make sense but this is not the target so we go through its list of neighbors the same way we did earlier but we check is this neighbor not already visited if that's the case we can add it to visit and we can add it to the q but if it is already visited then we don't do either of those things in this case it has one neighbor b and yes we're going to add this to the q and add it to visit so then this loop will stop and this loop will also stop because we went through every node in the q at that point and then we can increment our length so we know it took one it took a length one to arrive at this level next we check are we still executing the while loop well our q is not empty so we are we're going to take a snapshot of the length of the q it's one it's just one a node so we're going to run this loop once we're going to pop this node it's not the target so we're not going to return we're going to go through its list of neighbors it has two neighbors and each of them have not already been visited so we're going to add both of them to the visit hash set and add them to the q and then we're going to increment our length by one so it took a path length of two to get to this layer or this level of the graph and now we're going to run the while loop again we're going to start going through both of these nodes we're going to take a snapshot of this q it's going to be of length two because there's two of these here we're going to pop them we're going to let's say we pop c first we would pop it we would go we would check it's the target nope we would go through its list of neighbors it has a single neighbor which is e we would check has it already been added to visit yes it has so we're not going to add it again then we're going to end up popping the next one which this is the only one remaining we pop this is it equal to the result yes it is so we return the length it's two that means that the shortest path was length two and we know that because we went layer by layer these are all the nodes we could reach with a path length of zero these are all the nodes we could reach with a path length of one these are all the nodes we could reach with a path length of two and we find and this is the first time we encountered the result node so the shortest path to that node must be two and that's what we return. Now here the time complexity is going to be the same as earlier. It's going to be the size of the graph. But earlier we talked about the, for a matrix, the size of the graph was n times m. And technically what we didn't account for when we were doing that were the edges. This is the number of nodes in the matrix graph, but the number of edges for each node was four. So technically the time complexity for running BFS on a matrix is four times n times m. But we know we don't care about constants. So this is the time complexity we get here. But in this case, let's say the number of nodes is actually V for vertices, right? So that's the size of the graph. But how many edges could each node have? Well, technically V, right? Because remember, we learned earlier that E is going to be less than or equal to V squared because each vertex could have V edges. So if we're talking about edges for each node multiplied by the total number of nodes, it could be V times V, which is equal to V squared. But we don't write it this way because we know for sure here, that's not necessarily the case. This is not a full graph where every single node has the maximum number of edges. So to be more accurate, we could say the size of this graph is actually V, which is the number of vertices, because we potentially will have to visit every single one of these in the worst case with our B, with our BFS, we'll have to add each of the vertices to our visit hash set. But we might also have to travel along every single edge, which may not necessarily be equal to V. It could be greater or it could be less. So to be more accurate, we say that the time complexity for this BFS is equal to V plus E, where E is the number of edges in the graph. The space complexity, though, is a bit more simple. We know in the worst case, we could add every single node to the visit hash set and every single node to the queue. So the memory complexity is going to be big O of V, where that's the number of vertices, of course. Now before we finish up with graphs, I want to mention that we definitely learned a lot here. And that's because graphs are a very, very big topic in general, but also for coding interviews. There are a topic that comes up very frequently. But one thing we didn't talk about is what if these edges actually have some kind of weight attached to them? For example, the length of, you know, this edge is not just one. We've kind of been assuming each of these edges has the same length. We treat them the same. But what if, you know, the same way how cities are connected by roads that could be of different length? What if the length of this was two, this was three, this was also three, and maybe this one is 10? What would be the shortest path in that case? It would have been this over here, not what we had. We said the opposite. We said this is the shortest path. So our algorithm here would get that wrong. There is a much more complicated algorithm that could account for edges that have some weight or value attached to them. And if you want to learn more about it, I recommend checking out the advanced algorithms course. There's actually tons of graph algorithms that we didn't talk about, but they can get very, very complicated. There's a lot of academic research that's actually gone on in graphs. These are really complicated structures. But I think understanding DFS and BFS gives you a really, really strong foundation. After all, the shortest path algorithm that could solve this problem is actually based on BFS anyway. It's just a modified version. If you'd like to practice some graph problems, I recommend checking out the practice section and going to the graphs topic. Okay, so now let's finally move on to dynamic programming. Are you nervous?  Just kidding. Dynamic programming can be really scary for a lot of people, but I'm going to try my best to try to make it as simple as possible. And the first problem we're actually going to be looking at is one we already talked about when we were talking about recursion. And that is the Fibonacci sequence. And this is an instance of a one dimensional dynamic programming problem. Let me show you what I mean. But first, let's recall what the Fibonacci sequence is. Basically, the zero Fibonacci number is defined as being zero. The first Fibonacci number is defined as being one. An arbitrary Fibonacci number, the nth in this case is defined as being the n minus one Fibonacci number plus the n minus two. For example, the second Fibonacci number is equal to the first Fibonacci number plus the zero Fibonacci number. Therefore, the second Fibonacci number would be one plus zero, which is just equal to one. And then we could continue calculating the third and the fourth Fibonacci number and continue going just like that. Now if we wanted to calculate an arbitrary Fibonacci number, let's suppose the fifth Fibonacci number, we would do it using a loop, kind of how I just talked about right now, we would calculate the second and then we'd calculate the third, the fourth until we got to the fifth. It'd be pretty straightforward. We could do it in O of N time using a loop like that. What you might not realize is this is actually an instance of a dynamic programming problem. But to really understand the fundamentals of dynamic programming, I'm going to spend a lot of time analyzing it and showing you how we can take the recursive solution that we talked about earlier and convert it into a dynamic programming problem. Because that's what you'll normally be doing when you're when you start getting to more difficult dynamic programming problems. So when we solve this problem recursively before, we started with the decision tree. We wanted to calculate the fifth Fibonacci number. And we know to do that we have to get the fifth minus one Fibonacci number aka the fourth Fibonacci number and add it with the N minus two Fibonacci number aka five minus two aka three. And basically we keep drawing out this decision tree until we get to the base cases which are these two here. So let's continue doing that for four. We know we have to get the third and the second Fibonacci number. So for three, we have to get the second and the first Fibonacci number. And then here, we're going to do the same thing. Notice we're doing the same thing that we did over here, we're going to get the second, the first Fibonacci number for two, we're going to get finally to a few base cases one and the zero Fibonacci number. And for two here, we're doing the exact same thing. So this is some of the repeated work that you might be noticing. We're going to get the first Fibonacci number and then the zero Fibonacci number. And then one is already a base case. So we're not going to do anything. We know the first Fibonacci number is by definition equal to one. Now the only one of these we have to expand upon is this one over here. So to again, repeating the exact same thing we already did a couple places we have to say this is going to be the first Fibonacci number plus the zero Fibonacci number. Now the code for this approach would look something like this. So we have a recursive function. We know that if the Fibonacci number we're trying to calculate, let's say it's n is less than or equal to one, we're going to return n itself. So basically if n is equal to one, we return one. If n is equal to zero, we return zero. If that's not the case, we call our brute force recursive call in both directions, you know, n minus one is going to be the left branch and minus two is going to be the right branch. And then of course we would get to the base cases and then, you know, those would return up and those would return up and, you know, they would go all the way back up until we got to the root. The downside of this approach, though, is the height of this decision tree is going to be, you know, the Fibonacci number that we're trying to calculate. In this case, it's five. So the height of the tree is going to be approximately equal to five. The number of branches is going to be two. So in terms of big O of n, we would say that the, you know, size of this tree is going to be roughly equal to n. I mean, we can see that some of the levels aren't completely filled, but this is a rough upper bound. And in this case is what the Fibonacci number that we're trying to calculate is. But we see we're doing a lot of repeated work here. When we calculated the second Fibonacci number over here, you know, we had to draw out this subtree, this recursive subtree. And then we wanted to calculate the second Fibonacci number again.  And then, you know, we even had to do that a third time over here. But what's even worse than that is when we wanted to calculate the third Fibonacci number, we had to draw out an even bigger subtree over here, but we didn't only do it once, we had to do it twice. We had to draw out the same subtree over here. So what I'm getting at is there's a lot of repeated work that's going on. And there's a technique that we can use to eliminate this repeated work. It's sort of based on dynamic programming. So this technique of optimization is called memoization. We can basically take a brute force recursive solution. If we see we're creating a decision tree to solve the same sub problem, in this case, calculating the second Fibonacci number, we can cash that basically after we calculate it once, we can store that somewhere. So that next time when we're trying to solve the exact same sub problem, we don't redo all of the work. So in this case, we wouldn't even create these sub trees. We would automatically know what the second Fibonacci number is because we calculated it once. So in terms of code, you can see it looks very, very similar to the recursive solution. That's why when you're first learning how to do dynamic programming problems, what people do is they'll solve the recursive problem and then try to add memoization, try to add caching to it. And I still, to be honest, use this technique when I'm solving a difficult dynamic programming problem that I can't figure out. You can see when I call the brute force on passing in 10, but when I call the memoization I'm passing in five, please ignore that. You can consider this as a five. We're calculating the fifth Fibonacci number using the brute force way. And now with memoization, we're calculating it the memoization way. You can see we're passing in a parameter, which is the cash. Most commonly, I like to use a hash map to represent the cash, but you can also use a array, but I think it's easier using a hash map. So in this case, I'm actually going to draw our cash as a array because that's essentially what it is. We're mapping a integer. So in this case, you know, a Fibonacci number. So for example, in this case two, and we're then we're mapping it to the Fibonacci number, you know, basically the second Fibonacci number. So I'm going to draw it as an array, but we know we're actually using a hash map in this case. So initially, we pass in an empty hash map into memoization. So, you know, think of this as the empty hash map, we pass in five, we're trying to calculate the fifth Fibonacci number. Have we reached the base case? Is this a zero or a one? Nope. Is five already in our cash? Well, our cash is empty. By the way, this is an O of one operation to check if a value is in the cash. That's why we're using a hash map, but we could also use an array and it would be the same time complexity. In this case, five is not in our cash. So we call, you know, memoization, or you could call it whatever you want, but we're recursively going to check what the n minus one Fibonacci number is. In terms of the decision tree, we're going to start at five. Now we're going to check what the fourth Fibonacci number is. We're going to check the same base cases. It's not a base case. It's not already in the cash. Our cash is empty. So then we're going to call memoization n minus one. We're going to call the recursive function on three and three is also not going to execute any base cases. Then we're going to call memoization on two. This is where things are going to get interesting. So now we're at two. This isn't again quite a base case. It's not in the cash. So now we're going to call memoization on one over here, which is a base case. We know one is going to end up returning one because the first Fibonacci number is one. Then from two, we calculate the zero Fibonacci number. We know that's also a base case and that's going to end up returning zero. So here we're going to have one plus zero, add those together. It's one. So we found what the second Fibonacci number is. It's equal to one. So what are we going to do? We can immediately return it, but we're actually going to cash it before we return it because what we're saying is we just calculated the second Fibonacci number. If we ever need to calculate it again, which we know we're going to hear, we want to be able to calculate it immediately without having to make any recursive calls. So we cash that. So in our cash for the key value two, we're going to say the Fibonacci number is one. Then we're going to get back up to three. We calculated the second Fibonacci number. Now we have to calculate the three minus one, which is one, which is a base case. So here we're going to calculate the first Fibonacci number. It's going to end up returning one. So then we're going to add these two together, which is one plus one. The second Fibonacci number is one. The first Fibonacci number is one. Add those together. We get two. Therefore, the third Fibonacci number is two. So we're going to throw that in our cash. So for the key value three, the Fibonacci number is two. So now we know if we ever have to calculate the third Fibonacci number again, we don't want to have to repeat all this work. So we won't have to. And now again, things are going to get a little interesting. Now we're at four. We calculated the third Fibonacci number. It's time to calculate the second Fibonacci number. We could go through that whole recursive tree. But when we try to calculate the second Fibonacci number now, we're going to check, well, it's not less than or equal to one, but it is in our cash to the second Fibonacci number is in our cash. What is it? The second Fibonacci number is one. So that's what we're going to return. We're not going to do the recursive case. This is a base case. So we're going to end up returning one. So when we're trying to calculate the fourth Fibonacci number, we get two, which is the third Fibonacci number plus one. So the fourth Fibonacci number is three. And we can throw that in our cash and then return that up to the parent, which is five. So now we're trying to calculate the fifth Fibonacci number. We already calculated the fourth. Now it's time to calculate the third Fibonacci number. So we're going to recursively call that and we're going to see it's not less than or equal to one. But again, we check our cash and we found it. We found three in our cash. The third Fibonacci number is two. So basically we don't even have to execute this entire tree. We only have to check three. And then we immediately find the value, which is two. So we calculate the fifth Fibonacci number, which is three plus two. And that ends up being five. So we throw that in our cash. The fifth Fibonacci number is five. And then we return it. So you can see by cashing, this is all the work that we eliminated. So this is actually the size of our decision tree when we implement cashing. This is what it looks like. You can see that this essentially is linear to calculate the fifth Fibonacci number. We calculate the fourth to calculate the fourth. We calculate the third to calculate the third. We calculate the second. And to do that, we calculate the first. It's linear. I mean, technically, you can see that each of these nodes actually has a right child sort of. So you could say that actually the size is not just n, it's two times n, but we know that that's also still linear. It reduces to big O of n. So that's the overall time complexity. When we implement cashing, which is also called memoization, which is actually also called sometimes top down dynamic programming, this kind of diagram memoization and cashing is sometimes referred to as top down dynamic programming because we're starting at the top of the tree and then going down. There's actually another form of dynamic programming, which is generally a bit more difficult actually, because you can't just take the recursive solution and then add cashing to it. And it's called the bottom up approach of dynamic programming. And as the name implies, for this tree, we're going to start at the bottom of it and then work our way upward. So we're still not going to redo all of this work that we scribbled out, but we're going to start at the bottom of this tree and then work our way upward. And I'm going to show you that right now. So this approach where we don't use recursion at all is sometimes called the true dynamic programming approach. Like some people don't even consider memoization a dynamic programming. Some people only consider this to be dynamic programming, but this is also called the bottom up dynamic programming approach. So we would just pass in whatever Fibonacci number we're trying to compute, let's say in this case, n equals five. Here I wrote n equals 10. But to keep it simple, we're going to just calculate the fifth Fibonacci number. So we know we're trying to calculate the fifth Fibonacci number and recursively we saw that to do that, we have to get the fourth to do that. We have to get the third and to do that we have to get the second to do that. We have to get the first and to do that we have to get the zero, but why start here, which was the top and then go top down when we can go bottom up start at the base case immediately and then work our way upwards because when we have the base case, we can calculate well, this is another base case. But when we have both of the base cases, we can calculate this guy. And then we can calculate this guy. And And then we can calculate this guy until we get to the result that we actually want. So in terms of code, it would be pretty simple. Actually, this is the simplest code, I think of the three solutions, because it's essentially a loop. Now it can look a little bit complicated. And that's because I've really optimized this to the point that we don't even need an array, but I'm going to draw it this way just to get the main understanding across. First of all, if we have a Fibonacci number that's less than two, we're going to return, uh, you know, whatever N is. So the zero Fibonacci number, we know it's going to be zero. The first Fibonacci number we know is going to be one, but assuming we have N equals five, we're going to create, you know, this sub array. I'm calling it DP and we'll have this as our little sub array here. And now visually forgetting the code for just a second, visually, we would start here, we would want to get the second Fibonacci number. Now, how do we do it? Just take the two previous Fibonacci numbers, add them together. Zero plus one is equal to one. Now we want to get the third Fibonacci number. Add these two guys together. A one plus one is two to get the fourth Fibonacci number. Add the two previous together. One plus two is three to get the fifth Fibonacci number. Add these two together and we get two plus three equals five. We did the result. What was the time complexity? Big O of N. We just had to iterate, you know, N times roughly speaking. What's the memory complexity? Also big O of N. We're maintaining an array that we have over here. But my question to you is that is this array even necessary every time we got to a value when we were trying to calculate this guy over here, we only needed the two previous values. And then when we moved, when we calculated that and then we moved here, we didn't even need those values. We needed the two previous values here. We didn't need this guy anymore. So my question is, do we actually have to maintain the entire array? Or maybe we can get away with only saving the two previous values at a time. And that's exactly what we're going to do. So forgetting this portion of the array here, we only need an array of size two. And initially the values are going to be zero and one, just like we've drawn over here, but then we're going to get to I equals two. We're trying to calculate the second Fibonacci number. We're going to save this guy in a temporary variable. I'm just going to write it here. We're going to save one here. And then we're going to calculate in this position what the second Fibonacci number would be. It's going to be these two guys added together. Zero plus one is one. So what we would do is like overwrite this. We know in this case it's, you know, it was previously one and staying one, but I'm just doing this to get the point across. And then in the zero position, we would put whatever originally was over here in this spot, the good thing we saved it here. But in terms of code, we would save it in a temporary variable. So here we would now put one. So this is telling us we calculated now the second Fibonacci number and put it over here, and then we put the first Fibonacci number over here. Cause we know we're going to need the first and the second Fibonacci number. Now, when we take our I increment it by one and try to calculate the third Fibonacci number. And you can probably at this point see where I'm going here, but I'll quickly run through it just to get the point across. So we're going to overwrite the value here. Now by taking these two original values, one plus one, adding them together and then putting it over here. So now we have a two here and we were to put the original value, which was one, and then put it over here. It's already one, but you know, we're doing it anyway. And at this point, this would be the second Fibonacci number and this would be the third Fibonacci number. And now here we would take one plus two, add them together, replace this position with three and take the previous Fibonacci number, which was two and replace this guy with two. And then these two would be the third and fourth Fibonacci number. And at this point, we've sort of ran out of space, but you probably get the idea. We would now take these two, two plus three, add them together. We would get five. That's the fifth Fibonacci number. We would end up storing it in this spot. And then we would end up once our loop stops, which it would now, we would end up returning the value that's stored over here, which is five. So that's the fifth Fibonacci number. And of course, since we're looping end times, the time complexity is going to be big O of N, but we saved space. We didn't have to allocate the entire array. The space in this case is just an array of size two, which is constant memory. So our memory is not scaling as we increase our input N. So this is the most efficient way to solve this problem. And I hope this gives you an idea of the thought process that goes behind dynamic programming. Dynamic programming is essentially a technique that takes a big problem and then simplifies it. What makes this a dynamic programming problem is that we have originally a big problem. We're trying to calculate the fifth Fibonacci number. But to do that, we have to solve a sub problem, which is calculate the fourth Fibonacci number. To do that, we have to solve a sub problem, which is the third and another sub problem until we get to the base cases. So that's what dynamic programming is basically all about. Taking a big problem and then solving, breaking it down into sub problems, which Fibonacci number is a very good example of because it's mathematically a sub problem and then solving that sub problem. Most dynamic programming problems can actually be represented with equations like this. So this is the one dimensional case. Why this is considered one dimensional is because we have a one dimensional array, which is our solution space, right? We have to get the zero first, second, third, fourth, fifth Fibonacci number. It's one dimensional. So that must imply that there are two dimensional dynamic programming problems, which is correct. And that's what we're going to talk about next. So next let's move on to two dimensional dynamic programming and let's solve a pretty familiar problem at this point, counting paths. So we're going to be given a two dimensional grid and we were starting at the top left. We want to go to the bottom right and we want to count the number of paths that can lead us there. Now, in this case, though, there aren't any blockers like before we had zeros and ones, ones were blockers, but this time we don't have that. And we have another thing that's going to simplify things for us. We can only move down or move to the right. So that's going to make things pretty easy for us. So for example, one path would look like this. Another path would look like that since we can only move down or to the right, every path is actually going to be the exact same length. Because as we move down, we're getting closer to the bottom right. As we move to the right, we're getting closer to the bottom right. And, you know, eventually the paths are going to converge and they're both going to be the same length. Every single path to the result is going to be the same length. Now, based on what we learned in the graph section, we can do this recursively with depth first search. And so that's the brute force way to do this, but it's not going to be very efficient. So suppose we're given the number of rows and the number of columns. In this case, notice we actually don't care about the grid itself. It's not a parameter. What we actually care about are the dimensions of the grid. In this case, it's a square grid. So it's four by four, so four rows and four columns. And the input is going to be the starting position. We know it's going to be zero, zero to start with. So when I'm actually calling brute force, I'm passing in zero, zero as the starting coordinates and the dimensions are four by four. So we have some base cases. First of all, what if we go out of bounds? How are we going to go out of bounds in this case? Because our row is never going to be too small because we're starting here, but we can only move down. So if we go out of bounds, it's because we went too far out. Not because we went too far up. So when we reach this case, it'll be because our row is equal to, you know, four, which is the number of rows we have. So if R is equal to four, then we went out of bounds. Same thing with the column. We can only move to the right. We can't move to the left. So that simplifies things for us. So when we go too far to the right, so if C equals the number of columns, we can return zero. That basically means we went out of bounds. There's no valid path that goes out of bounds that reaches the result. The other base case, of course, would be if, you know, we did reach the goal. So that would be if R is equal to rows minus one and column is equal to columns minus one, in that case, we would return one. That means, OK, this is a path. Otherwise, suppose we're actually starting from here. It's not a base case. So what we would do is call brute force two times because we can either go down. That's this first case where we say row plus one or we can move to the right where we say column plus one. So brute force, this is going to basically be a decision tree with two branches because for every position, no matter where we're at pretty much, we can either go down or to the right. We can't go in four directions. We can only go, you know, in two directions. So this decision tree has two branches. What's the height of the decision tree going to be? Well, like I said, every path is going to have the same length. So any path in our decision tree is going to have the same height roughly. And the height is basically going to be the number of rows plus the number of columns, because that's practically what the length of every single path to the destination is going to be. So we can say that the time complexity is two to the power of n plus m, where let's say these are the dimensions of the grid. So I've written that up here as well. So that's the time complexity. So obviously it's not very efficient. But we can make it much more efficient. Basically, the time complexity can be reduced to the size of the grid because we're going to notice some repeated work. First, I'm going to quickly walk through a little bit of the brute force. And then we're going to see how we can use cashing to improve the time complexity. So first we start here, we go down and we go to the right. So now we want to know how many ways can we reach the destination from here and from here? Well, from here, we're again going to go to the right, or we're going to go. We're going to go down or we're going to go to the right from here. We're going to do the same thing. Go down or to the right. And then, you know, from here, suppose we're going to go down and to the right. And then from here, we're going to go down, which is a base case. That's going to return zero. And we're going to go to the right over here. From here, we're going to go down can't do that. We're going to go to the right as well. From here, same thing. But finally we get to the destination. This is going to return one for us. So when we're calculating how many ways from here, can we reach the destination? We're going to have a value of one now. What about from here? Well, here was zero because we went out of bounds, but from here was one. So we're going to take those two results, add them together and we get a one over here. Same thing for this guy. There was a zero here and a one here. So add them together. We get a one. Now finally, when we get back up over here, we have the value below, but now we're trying to calculate the value that's over here. Well, from here, we can have two choices.  We have the value down here, but what's the value over here? We don't know. We have to go down and we have to go to the right. Well, what about from over here? Again, we can go down and to the right. Well, right is out of bounds. That's going to return zero down is reaching the destination. That's going to return one. So add those together. We get a one over here. Now we can calculate what goes over here one plus one. So add those together. We get a two over here. What about in this position? There's a one over here and there's a two over here. Add those together. We get a three in this position. Then we can calculate what goes over here. One plus three, add those together. We get a four in this position. So now you're starting to get the idea. So as we try to calculate starting from here, how many ways can we reach the destination? We pretty much have to find the, we have to solve the sub problem for every other position because to solve this problem over here, we have to solve these two problems. But to solve these two problems, then we have to solve these next three problems. And to solve those, we have to solve these and et cetera, et cetera. We have to keep going until we get to the base case, which is the result and then work our way back to what we were originally trying to do. When you do this recursively and then add cashing to it, which I'm going to go over right now, this is called the top down dynamic programming approach. But as you might have noticed, we can eventually also work our way starting from the bottom and then work our way up, which is going to be the true dynamic programming approach, which is called the bottom up approach. But for now, let's focus on taking this brute force and adding cashing to it. So let's undo a little bit of this work and go back to some of the basics that we were talking about over here. For every single position, no matter what it is, we can get how many ways from here can we reach the result just by taking the value below it and the value to the right and adding those two sub problems together and then assigning it over here. But notice something. If we want to solve this sub problem, we have to solve this sub problem and this problem, but if we want to solve this sub problem, we have to solve this sub problem and this sub problem. Well, we have to solve this sub problem twice. That's where the repeated work is coming in. And it's going to get worse and worse from here, we have to solve this and this from here, we have to solve this and this. From here, we have to solve this and this, this is being done twice. As you can see, this is being done twice. As you can see. So there's a lot of repeated work going on. And I can draw out the entire thing. I encourage you to do that if you want to have a better understanding of it. But the idea is there's going to be a bunch of cells that have repeated work. And it's going to be exponential because you can see that there are two different ways that we can land in this spot. That means there's going to be two different ways we can go move to the right over here. There's two different ways that we can land in this spot. So there's going to be two arrows actually going down here, two arrows going to the right. So it's going to get more and more and more. And if we had a really big grid, it would be very, very inefficient. So cashing is going to help us a lot here. So in terms of code, the good thing is about cashing. There's very few changes that you actually have to make here. So essentially, the first base case is going to stay the same. And the second base case is going to stay the same. But in between that, we're going to add the case where if our cash, which in this case is a two dimensional array, which is going to be the exact same size as our input grid. Well, technically, we don't have a grid, but the cash is going to be of the dimensions of that, you know, input. And you could also use a hash map if you wanted to. Generally, I prefer to use a hash map. But in this case, we're using a two dimensional grid. And our memoization solution has an extra parameter for that two dimensional grid cash that our brute force did not have. And when I'm passing in a grid here, you know, this is kind of complicated. If you're not familiar with Python, this is essentially creating a two dimensional grid with all zeros. That's a four by four, essentially, if you are familiar with Python, you still might not understand this because this is, you know, kind of a weird syntax. Essentially, we have an array of size one with a zero inside of it. We multiply it by four, which gives us an array of size four with four zeros inside of it. And then we create a outer array taking that array and creating four copies of it. That's where this comes from. And that gives us basically four by four grid with all zeros inside of it. It's a lot easier to do this in most other languages, thankfully. But when we have that cash, if we don't go out of bounds, so take this, for example, we went down and to the right. And then from there, we went down and to the right. And then from here, we went down and to the right. But in reality, one of these is going to execute first. Let's say this one executes first. And then we calculate how many ways from this position we can reach the result. And once we have that, we're going to add it to our cash. So you can think of it, think of this grid as being our cash. We're going to put the value here. So as we saw before, all the values in the bottom row are going to be one. That makes sense because from here, we can't move down. We can only move to the right. So from here, there's one path that can lead us to the result. And from here, there's one path that can lead us to result from here. There's one path that can lead us to the result. The next row we already filled out earlier looked like this. So now let's briefly go over filling out the rest of it. So from here, we want to calculate the value. We go down and to the right. We don't have the value here. Let's go down and to the right. We don't have the value here. Let's go down and to the right. There's nothing on the right, but below there's a one. So here we can put a one as the result. Now we can calculate the value that goes here to plus one, that's going to be three. Now we can calculate the value that goes here, three plus three is six. And we can calculate the value that goes here for plus six is 10. So now when this guy wants to go down and to the right to calculate the value that goes here, we already have the value that goes here. We cashed it by building this grid. We added it to our cash. We're not going to run DFS. We're not going to run, you know, our recursive call from this position again and do all that repeated work. We don't have to do that anymore. So from here, when we go down, we're going to check, is that value out of bounds? Nope. Is that value in our cash? Yes. So we can return that value in our cash, which is six, but we still have to calculate the value that goes over here. By the way, the order of this is somewhat important. Now these two could be swapped. You don't have to put them in this order, but it is important that we put this before this because we have to check if we went out of bounds before we try to index this two dimensional array, because if we index it with, uh, you know, an R or a C that's out of bounds, then we're going to get an exception thrown or an error or something like that. So this is usually the first check that you want to make. You want to make sure we're not out of bounds. That's really important. But otherwise, if none of the base cases execute, we're basically running the same thing we did with our brute force. We're running the recursive call, you know, going in both directions, either R plus one or C plus one, passing in the same, you know, hard coded values, rows, columns, whatever, and passing in that cash, which is a reference to the object. We're not creating a new cash every time we call the recursive function. We're only creating a single cash initially, and then reusing that throughout the recursive calls. And then when we add the result of those two together, so in this case, we're going to recursively call memoization over here, we're going to go down and to the right. And from here, we're going to go down and to the right. This is going to be a zero. There's a one over here. Add those together. We get a one here. What value goes here? Three plus one. So we get a four over here. Now we can finally calculate what goes over here. It's six plus four. So there's 10 ways from here that we can get to the destination. There's 10 ways from here that we can get to the destination. Add those two together. That means there's 20 different ways from the starting point that we can get to the destination. And these are all unique paths. So this is something how it would play out if we did it recursively with memoization. But as you kind of saw, why should we even start at the top and work our way down and then recursively, you know, solve the sub problems and then go back up? Why not just immediately start at the bottom and then fill in these values and then get all the way to the top and ultimately have that result anyway? Well, the time complexity will still be the same because we still have to pretty much fill out this entire grid. As you saw right now, the time complexity is the size of the grid. We're not doing any repeated work. But in this case, we also have to declare a bunch of space. We have to create a two dimensional grid, which is going to be the same size. But the benefit of dynamic programming is sometimes we don't have to declare all that extra space as we saw with the Fibonacci sequence. We were able to save space by using the bottom up approach. The same is true with this problem. Let me show you what I mean. So this is what the code for the true dynamic programming, aka bottom up approach would look like. It's usually pretty short for dynamic programming problems. The bottom up approach usually has a lot less code than the recursive approach, but it's usually difficult to come up with unless you have a good understanding of the recursive approaches. And there are many dynamic programming problems that follow the same pattern of having a two dimensional grid and you know, solving sub problems that are below and to the right and then eventually arriving at the solution. So in this problem, what we're going to do is start bottom up. We're going to start at the base case and then calculate these values and then go here and then calculate these values and then keep going like that. Now it's intentional the order that we're solving these sub problems. And we kind of have to do it this way, starting at the last row, going to the left, starting at the next row, going to the left, because well, this is the base case and for us to know this value, we have to get the bottom value. Good thing here is for the last row, there's nothing below. We can just kind of assume that there's a bunch of zeros here if we really want to. And that's sometimes a technique that's used in more complicated two dimensional dynamic programming problems. In this case, we'll look below that'll be zero and we'll look to the right. And what we expect from here is that there's a one there. Now it doesn't really make sense that from here, how many paths are there that can lead to this position? Well, is there one path or is there zero paths? Technically to me, it makes sense that there would be zero paths. But as the base case, we put a one here because that's just what allows our math to work out. If we put a zero here, then the value we're going to get here is going to be zero and then here and then here and then all of these are going to end up being zero. We know that's not correct. So we put a one here. And then when we want to calculate this value, we go below into the right, we take this at it, and then we get a one here. And so we have to compute it like this. And then when we want to get to the next row, we already have all of these populated. So for us to calculate this position, we look below into the right, there's nothing there. And we already have the value populated here. So we'd get a one here and then we can populate this value only after we've gotten these two, we can add them together and get a two here. So it's going mostly in the same order that our recursive algorithm did. And the memoization one did is just we're immediately starting at the bottom and working our way up. We're not even making the recursive calls starting from the top. So in terms of code, it would basically be the exact same thing. What we're going to do here is declare a previous row, which is going to be all zeros. What that basically is, we're implicitly creating a row over here. That's just telling us that there's all zeros over here. And then we're iterating through this 2d grid starting here, you know, starting in the last row and then going up and up and up. And in our nested loop, we're starting at the last column and then working our way to the left. Well, technically we're not starting at the last column. We're starting at column minus two, the number of columns, which in this case would be four. That's what we're passing in here for minus two. So we're starting at the second to last column. Why am I doing that? Well, because we know that the base case is going to be one anyway. So we actually fill in that base case, we create a current row. So this is going to be our current row. And we're going to fill in a one at the last position. And we actually know that for every row, the last value is going to be one because we know from any of these going down, there's only one way to reach the destination. We can't go to the right for any of these anyway. But notice how we're actually not creating a 2d grid because it's not necessary. Notice how to fill in this entire row. All we need is the previous row, aka the row below it. And that's enough. We don't need anything from the row above or the row above that. We just need the row below it. And to get the values in this row, we only need the values below that row. So at any given point, we're only going to have two rows in memory, the previous row and the current row. So the space complexity is going to be two times the number of columns. Let's say M is the number of columns. So this is the space complexity. This can be reduced, of course, to big O of M, because we don't care about constants. So that's the space complexity of this approach. Clearly the time complexity, we are having to still iterate through the entire grid. So the time complexity is still going to be N times M.  But this is basically starting at rows minus one. And this is starting at columns minus two, you know, this column. And this is basically saying we're going to keep going until we've gotten to the zeroth row, and we're going to stop as we get to the negative one row. So we're not going to execute when we get to the negative one row, and we're not going to execute when we get to the negative one column position. That's why we have negative one here as well. And the last negative one basically means we're decrementing each time. So we're going to take the column, decrement it each time. In most languages, I think it's a little bit more obvious what the four loops are doing. And we have the code for those below if you want to check them out. So at this point, you probably get the idea and I bet you could fill in this grid yourself if you really wanted to. But I'll do it really quickly. So when we want to calculate the value here, which is current row, we're going to take the current row column plus one. So that's our way of looking to the right, we take the current row and get the column plus one to get the value below, we take the previous row in the same column. So we take those add them together and then assign that value here. It's going to be one. We're going to do the same thing here and here they're all going to be one. Now, before we start looking at this row, we're going to take our current row, which was this and assign it to previous row. So this is now going to be considered our previous row. This is no longer going to be in memory. And now here, we're going to create a new current row of the same dimensions. It's going to initially be all zeros, but we're not going to care about that. And the last value here is going to be a one. And then we're going to start calculating these. This one is going to be one plus one, two, this one is going to be three, this one is going to be four. And then we're going to do the exact same thing over here. This is going to be out of memory. This is going to be the new previous row. And this is going to be the new current row. There's going to be a one here. This is going to get a three, this is going to get a six, this is going to get a 10. And again, this is going to be removed from memory. This is going to be the new previous row. And and this is going to be the new current row. There's going to be a one here. This is going to be four. This is going to be 10. This is going to be 20. And then finally, we're going to delete this from memory as well. This is going to be our previous row. We're going to return the zero value in that previous row. That's exactly what we wanted. We're going to return the 20. So this is, believe it or not, a relatively simple two dimensional dynamic programming problems. They can get a lot harder. But if you can get really good with the concepts that we talked about here, but, you know, understanding the idea of decisions that we're making, not doing any repeated work and basically filling in the values of a grid, you can go very, very far with more difficult dynamic programming problems. If you want to practice some, check out the practice section and look at the problems in the two dimensional dynamic programming topic. So now finally, the last topic that we're going to cover is bit manipulation. And the reason that we're covering it last is because I think it's not really a super important topic, especially for coding interviews, but it's definitely something that comes up. So I think it's very important to at the very least understand some of the basic things that you can do with bit manipulation and even beyond coding interviews. I think it's good to have a fundamental understanding of the basics. So there's a few logical operations that you can do with bits. Now, first of all, what is a bit? Well, we talked about it close to the beginning of the course. You know, bits are just zeros and ones. Computers basically use zeros and ones exclusively under the hood, but most of that ends up being abstracted for us. But let's start with a few fundamental operations. One is the and operation. So with zeros and ones, we can do a logic and aka a bit wise and so for two given bits, suppose zero and zero. Now we usually use this character, the ampersand character to indicate a bit wise and and that's actually the case for most languages. So I'll summarize the main operations in terms of code. Now this is Python, but actually these operations are pretty much the exact same in most languages. So the logic and operator is going to use this character. So zero and it with zero is the value zero. So basically what the logic and means is that both bits have to be one for the result to be one. But if that's not the case, the result is going to be zero regardless. So if the first bit is zero and the second bit is one, then the result is still going to be zero. If the first bit is one and the second bit is zero, again, the result is going to be zero. But only in the last case where both bits are one is the result going to be one. So that's where the name comes from. And both have to be one and then the result will be one or is sort of the opposite. Only a single one has to be one and then the result will be one. But if neither are one, then the result will be zero. So this is the character for logic or and so continuing zero or one will be one because only one of these has to be one. And then if the first one is one and the second one is zero, the result will again be one because only one needs to be one. And if both of them are one, the result will be one. The third case is called exclusive or and this actually does come up occasionally in coding interviews. It's basically the result will be one only if one of the bits is one, not if both of them are so it's similar to or except it's exclusive or only exclusively one of these can be one and then the result will be one, not if both of them are one. So the character for that is the up carrot kind of so zero exclusive or with zero is going to be zero. Exactly one of these should be one for the result to be one. It's not so we don't get a one. But if we have the second one is one, then we get one in the result. If the first one is one, then we also get a one in the result. But if both of them are one, we get a zero in the result. So you can kind of take a look at these three and compare them. They're mostly straightforward. But if you haven't seen this before, if you've never seen these, these are called truth tables. Basically, these are some logical operations that we could do. This is not something you'll necessarily have to draw out in like a coding interview, but it's good to kind of understand the logical basics of what's going on here that now, of course, there's the negation operator, which is the tilde in most languages. It'll just take any bit and take the negation of it. So, you know, if we take the negation of one, it's going to be zero. If we take the negation of zero, it's going to be one. It's pretty straightforward. These are really the only two cases. The last thing is bit shifting. So if we have some binary integer, usually in programming languages, we're talking about 32 bit integers, but I'm not going to draw all that out because, you know, we take up a bunch of space and it's not super important to get the idea across. Let's say we had an integer that, you know, was zero zero one. So basically, this is the integer one in binary representation. Of course, we could draw out all 32 digits, but we're not going to in this case. Now, we take this and your bit shift it to the left by one. That's what we're doing down here. We're taking n, which is one and shifting it to the left by one and then assigning that to n. So what this would do is it would just take all these bits and then shift them to the left by one. So by doing this operation, we would get a result of this. What if we did this operation again on this integer now? Well, then we would get a result like this. What if we did it one more time now? Well, assuming in this case, we just have an integer with three bits and we have no bits, you know, to the left of it. Well, if we bit shift this one more time to the left, where does the one go? Because previously we were seeing every bit was shifted to the left. Well, in this case, we have a one here. It's going to get shifted to the left and then it's essentially going to be dropped off. It's going to be deleted. It's going to be replaced with a zero. It's not it's not going to circle back here. It's just going to completely be deleted and then we would have this as the result. This zero would be moved to the left and, you know, when this zero is moved to the left, it's going to be always replaced with a zero. That's what we kind of saw throughout this example. When we shifted this by one, it was replaced with a zero. When we shifted this again, replaced with a zero. Now, one thing that's very important when we have a binary value, let's suppose we have one zero one one. This is the ones place, right? This tells us how many ones we have. That's how numbers are represented in binary. The next digit is going to tell us how many twos we have. So this is the twos place and then the next digit is going to be the fours place and the next digit is going to be the eights place and it's going to keep going like that. Now, this is somewhat comparable to if we were, you know, suppose I had base 10, if we were thinking about integers in terms of base 10, which is what we do most of the time. We're all used to thinking of numbers where the max of where the max value a digit can be is nine. And then if we get the value 10, we of course add a new digit for that. Right? We count one, two, three. We go all the way up to nine and then when we get to 10, we add a new digit for that. That's called base 10. This is called the base two because by the time we started at zero, then we get one by the time we get to two, we add another digit for that. So this in binary is not the number 10. This is the number two. That's why this is the ones place. This is the twos place. This is the four's place, eight's place, et cetera, et cetera, right? Each time we move to the left, we're getting a new power of two. So essentially this is two to the power of zero. This is two to the power of one. This is two to the power of two to the power of three, which is eight. And it keeps going like that. That's how binary numbers work. Whereas with base 10, you have a number like this. This is the ones place, aka 10 to the power of zero that evaluates to be one. This is the tens place, right? This is not three. This tells us we have 30 because it goes in the next spot. So this is 30, right? We're pretty familiar with that. That's basic math, but we call this the tens place, aka 10 to the power of one. This is the hundreds place. This isn't four. This is four hundred, right? So this is 10 to the power of two. 10 to the power of two, by the way, is a hundred. So it keeps going like that. This is the thousands plates, et cetera, et cetera. That's why we call this base 10. So I wanted to kind of review that with you in case you weren't already familiar. And by the way, what happens if we take this and shift it to the left by one and we got something like this five times five, four, three, two, and then we add a zero in this spot similar to how we were doing it with binary. Well, shifting to the left and adding a zero when it comes to base 10 is essentially taking this and multiplying it by 10. If you're familiar with math, you know, you know, multiplying by 10 essentially adds a zero. Well, in terms of binary, when we're shifting to the left by one, we're actually multiplying by two. That's very important. That's a pretty basic and important idea to remember as you shift to the left, you're multiplying by two. This in binary is the integer one. This in binary is the integer two, because we have, you know, something in the two's place. This in binary is the integer four, and it basically keeps going like that. So that's bit shifting to the left. We can also bit shift to the right. So suppose we had a value like this. By the way, this represents the value four in binary. Suppose we shift to the right by one. We would get something that looks like this. Suppose we shift to the right by one again. We would get something that looks like this. Notice how as we shift, we took this one, moved it to the next position, and then we replaced what was on the left with a zero. That's similar to what we did when we were shifting to the right. So now we're going to shift to the right one more time. We're going to get basically zero. And similar to how when we shifted to the left by one, we were multiplying by two. When we shift to the right by one, we're dividing by two. This is four, this is two, this is one. And this is zero. So we're dividing by two when we shift to the right. But if we have an odd number, we're going to round down. So with all that being said, let's jump into an example problem where we're given some integer and we have to count the number of bits. So suppose we were given an integer like 23, which by the way, in terms of binary would look something like this. In most languages, it would be represented with a 32 bit integer. So we would actually have 32 bits, you know, in this case, we would just have a bunch. So in this case, we have five bits. So we would have probably 27 zeros that come before it, which would make this a 32 bit integer. But let's just draw out the five bits for simplicity's sake. And suppose we want to, given this integer, count the number of bits. Now, N in this case is going to be 23 base 10. But we know under the hood that's represented by some binary value that will look like this. So we want to count the bits of its binary representation. How can we do that? Well, we're basically going to use the same ideas that we talked about over here. Or we're given that as a parameter, we're counting the number of bits. Initially, that's going to be zero while N is greater than zero. So suppose we're given an integer like 23 and we want to count the number of one bits in its binary representation. Well, in terms of binary, it would look something like this one zero one one one. Now, most of the time, you'll be using a 32 bit integer to kind of store this. Python actually has unlimited bits for values. But let's suppose we had 32 bits, basically, since this is five bits, we would have 27 more bits, which are all leading zeros. So I'm not going to draw all of those out. We're just going to focus on these. And we want to count the number of one bits in its binary representation. So N in this case is the parameter. It's going to be 23. But we know every base 10 integer has some binary representation. In this case, this is what it looks like. We want to count how many one bits it has. In this case, it has four. But how can we count how can we count them algorithmically? Well, it's not too complicated. We just need some of these operations that we already talked about. So in our function, we're given the parameter. We're going to declare a count, which is going to be the count of one bits. We're going to count while our value N is greater than zero. We're assuming we don't have to worry about negative numbers in this case. And we know that the value zero itself, even in binary, will just be 32 zero. So there's not going to be any one bits for that anyway. So now we're basically going to count one by one. We're going to check the ones place. Is there a one bit here or is it zero? How do we know? Well, we can use the logic and operator, the bitwise and by taking N, which is right now 23 and a bitwise ending it with one. We're going to get an operation that looks something like this. This is what one looks like in binary. Of course, it would have a bunch of more zeros, but we don't care about those zeros. So when we bitwise ended single digits, we, you know, we had this truth table over here and this will help us out when we bitwise and multiple bits. It's basically taking each of these and taking the law, the bitwise end of them. So we know that for these two, it's going to be one. And for this, it's going to be zero for this, it's going to be zero for this. It's also going to be zero and for this, it's also going to be zero because both of the bits have to be one for us to get a one in the result. Now, let me tell you something. When we take any number and bitwise and it with one, the result that we get is always going to be either zero or one. The reason is because this is one in binary. It has only zeros here. So we know everything in the result is going to be zero. Except possibly this digit.  If this digit is a one, we're going to get a one in the output. If this digit is a zero, we're going to get a zero in the output. We're we're using the value one because it's special. It has all zeros except for this bit. So this will tell us if we have a one in the ones place or not. So in this case, we are going to get a one. So this is going to evaluate to true. So then we're going to increment our count by two. And then what we're going to do is take our end and shift it to the right, which we know is the same as dividing by two. So when we take this and shift it to the right, we get something that looks like this, right? We're basically chopping off this bit. We don't care about it anymore. Then we're taking the rest of these, shifting it by one, and then we're placing the leftmost digit with a zero. Now we're just going to repeat the same thing until this value becomes zero. So we're going to take the digit one, the value one bitwise and these together. In this case, we're going to get a one in the output because this is a one. And then we're going to increment our count by one again. So so far, our count is two. We've counted two one bits and we're going to basically do the same thing. So now this is going to be shifted to the right by one. We're going to get something like this as the value. We're going to, you know, check is this a one or not by taking the bitwise and it is a one. So now our count is going to be three. And then we're going to shift this to the right by one. We're going to get something that looks like this. Now we're going to bitwise and this. So we're going to check is this a one or not? We're going to get a zero. So this is not going to evaluate to true. So we're not going to increment the count by one. Our count is still three. And then of course, lastly, we're going to take this, shift it to the right by one. We're going to finally get this. We're going to check is this a one bit or not it is. So we're going to increment our count. Our count is now going to be four. And then we're going to shift this to the right by one again. And at this point, it's going to be five zeros. So our conditional is not going to execute anymore. So our loop is going to stop. And we're going to return the count that we calculated, which is four. So we had four one bits in this particular integer, which is 23. So 23 has four one bits. So we didn't go super in depth in this because I don't think it's super worth going into. I think understanding the basics is probably enough. And there are some practice problems in the practice section. If you want to practice more bit manipulation type problems, usually they just require a bunch of tricks, which is why I think they don't really come up super often in coding interviews because they don't really make for good coding interview questions, either you know the trick or you don't. So they're not the best coding interview questions, in my opinion. But these basics that we talked about definitely can come up even outside of coding interviews. So it's good that you have now learned them.