Learn Dynamic Programming with Animations – Full Course for Beginners

Key Takeaways

Master the art of dynamic programming by learning to break complex challenges into simple reusable subpros. This course features step-by-step animations that bring abstract logic to life, showing you exactly how data flows through tables and recursion trees in real time. Develop a powerful visual intu intuition for optimization so you can solve even the toughest algorithmic puzzles with ease. Sheldon created this course. Dynamic programming is one of the most powerful tools for solving coding interview problems, but it can feel overwhelming at first. In this video, we'll break down the main DP patterns step by step in plain terms and with clear visual examples so you can actually understand what's going on and start solving DP problems with confidence. Hi, I'm Sheldon, an exooler with 10 years of experience, and I help you prep for coding interviews on the Algo Monster platform. Good news, you don't need to memorize hundreds of problems to get good at dynamic programming. You just need to master a small set of patterns. Most DP problems are variations of the same ideas. And once you recognize those patterns, new problems become much easier to solve. So that's what we'll concentrate on, but we'll start from the fundamentals and build up from there, one concept at a time. Let's look at a popular problem. There is a staircase with n steps. You are at the bottom and want to reach the top. And there are two possible moves. Climb one step at a time or jump two steps at once. and we need to count how many different ways there are to reach the top. To understand it better, let's look at a simple example. A staircase with three steps. What options do we have here? We can climb one step three times in a row or take one step then jump two. Or you can jump two at once and then take one step. But when the number of steps grows, for example, to 10, counting the options by hand becomes difficult. So it's better to write code that quickly calculates all possible paths. Where do we start? Let's think about how you can get to a step. First, consider the simplest cases. For the first step, there is only one way to get there. You take one step. But for the second step, there are already two ways. You either take two single steps or you make one big jump straight to the second step. And now, let's move on to the third step and just continue with the paths we already know. At this point, we already have all the ways that lead to step one and step two. So each of those paths can be extended to reach step three. Paths that led to step two can add one more step up. And paths that led to step one can be extended with one jump directly to step three. So nothing new really appears here. We're only extending existing routes. That means the total number of ways to reach step three is 1 + 2. So it's three ways in total. In other words, all paths that end at step two are already counted. And when we add one more step to reach step three, we don't create a new path. It's the same path just extended by one step. The same idea applies to the path from step one to step three. We simply continue it without creating anything new. Now let's see what happens with step four. Here the same logic of extending existing paths applies again. First option, we reach step four through step three. Everything we already counted for step three. All three routes can take one more step to reach step four. These are not new paths, just the same routes extended to the top of the staircase. And the second option, we jump directly from step two to step four. For step two, we already have two different paths, and we add one jump to each of them to reach step four. Once again, we're just extending the paths we already had. In the end, all paths found for the two previous steps are simply extended one more step forward. And for step four, we get three ways through step three plus two ways through step two. Total five ways. So the idea is this. We only count distinct routes for the two previous steps and then extend them. The same path can never be counted twice. We only expand it by one more step or jump. If we generalize this rule, we get that the number of ways to reach step in is the sum of the number of ways to reach step n minus one and step n minus two. simply because you can only get to step in from the two previous ones. Now that we've derived this rule, let's implement it in code. But let's start with the simplest situations first. If you need to reach the first step, so n equals 1, there's only one option. You take one step. That's our first base case. Next comes the second step. Here there are two possible ways. Either two small steps or one big jump. This is our second base case. And for all other steps, we use the rule we've already discovered. The number of ways to reach step n is the sum of the ways to reach steps n minus one and n minus2. Now the natural question is how do we actually get these two numbers? This is where recursion comes in. The function simply calls itself. First it asks how many ways are there to reach step n minus one and calculates it recursively. Then it asks the same question for step n minus2. Since the function itself knows how to compute the number of ways for any given step, the values it returns are exactly what we need. All that's left is to add them together. But to really see how this works, let's walk through the recursion step by step. Let's start with step three. That is n equals 3. We call the function and go through the first two checks. 3 is neither equal to 1 nor to two. So we move on to the formula to compute the number of ways to reach step three. The function first calls itself for step two and this immediately returns a value because step two is one of our base cases. Then the function calls itself for step one. And that also immediately returns a value since step one is a base case as well. Now we have both numbers. So we simply add them together. 2 + 1 gives us three. And that's exactly the value the function returns. Everything checks out. Now let's go one step further and look at step four. If n= 4, the function again follows the same logic just one level deeper. First it calls itself for step three. Inside that call, the function again needs the values for steps two and one, both of which are base cases. For step two, the answer is two. For step one, it's one. Adding those gives us the result for step three, which is three. That's the first part. Next, the function also needs the number of ways to reach step two. But since that's a base case, we already know the answer is two. Now, we can apply the formula for step 4. 3 + 2. So, the result is five ways to reach step four. And once again, everything works exactly as expected. But here's the problem. What happens if we call the function for step 40? Well, the calculation will take a very long time. But why does that happen? To understand this, let's look at the recursion tree for step six. If you look closely, you'll notice that the number of ways to reach step three is calculated multiple times. It's needed when we compute step four. It's needed again for step five. And since step five itself depends on step four, that same calculation shows up there again. The core issue is that our function doesn't remember any previous results. So every time the calculation for step three appears somewhere in the recursion tree, the function recomputes it from scratch, the exact same work is done over and over again. As n gets bigger, the recursion tree grows larger and larger and the number of these repeated calculations explodes. And this leads to the most important point. The number of recursive calls grows extremely fast. In fact, the time complexity here is O of 2 to the^ of n. That means that even for n= 30, we already end up doing about a billion repeated computations. Okay, so we found the inefficiency. But the real question is how do we avoid recalculating the same values over and over again? What if the very first time we compute the number of ways to reach a step, we simply store that result somewhere? Then every next time we need it, we can just reuse it instead of recmputing everything. If we want to store results, we obviously need some kind of storage. So what should it look like? Think about it this way. When we compute the number of ways to reach step three, we'd like to save that value. And the next time recursion reaches step three, we want to immediately return that saved result. The step number works perfectly as a key, and the number of paths is the value. That makes a hashmap a perfect fit here. Now, let's walk through how recursion changes with this idea in place. For example, when we want to compute the answer for five steps, we start with n equals 5. Before doing any real work, the first thing we do is check the hashmap. Maybe there's already a stored result for step five. There isn't. It's still empty. So, we continue as usual and break the problem down into steps four and three. We move to step four. Again, we check the hashmap. Still empty. So, we break this down further into steps three and two. Next, we reach step three. Once again, nothing is [clears throat] stored yet. So, we need the values for steps two and one. Step two is a base case. We know there are exactly two ways to reach it. The same thing happens with step one. It's also a base case. So, we just get it instantly. Now we finally have everything we need to compute step three. We add the values together, get the result. But now before returning, we store it in our hashmap because it's a new value we calculated. And up to this point, everything looks very similar to what we had before. But now comes the important difference. Look closely. We move back up to step four. We already have the value for step three, and we also need the value for step two. When recursion reaches step two, we instantly return the result because it's the base case. We add the two values, store the result for step four in the hashmap and return it. And now comes the best part. We're back at step five. We already have the value for step four. Now we also need the value for step three. Normally this is where recursion would again break step three into steps two and one. But this time it doesn't. We check the hashmap, see that step three is already there, and instantly return it. No extra recursion at all. See what's happening? Instead of recomputing everything from scratch every time, we store intermediate results and reuse them. This saves a massive amount of time and resources. For example, if you look at the recursion tree for six steps, you'll notice that all those duplicate computations simply disappear because every value is computed only once. And the larger n gets, the more powerful this optimization becomes. Now, let's summarize what the code does conceptually. First, we create an empty storage, a hashmap, where we'll keep all computed results. Then inside the function, the very first thing we do is check that storage. If the answer for this step was already computed, we return it immediately and stop. If not, we check the base cases just like before. If those don't apply, we compute the number of ways recursively using our formula. But now there's one extra step. After computing the result, we store it in the hashmap using the step number as the key. That way, the next time we need this value, we can instantly reuse it. Only after that do we return the result. And what we've just done is called memoization. A technique where we store the results of previous function calls so we don't recomputee the same thing when the same input appears again. In other words, memilization is recursion with memory. We still solve the problem top down, but every answer we discover gets saved. So future calls can just grab it from storage instead of doing the work again. In practice, memalization is one of the fundamental and most powerful techniques in dynamic programming. It shows up in a huge number of problems and can dramatically speed up solutions. Without memorization, this algorithm has exponential time complexity. But with memoization, the time complexity drops to linear O of N because we compute each step only once. And since there are only N steps, the total work is linear. The memory usage is also O of N. We store at most N values in the hashmap and the recursion depth will never exceed N either. Because of this, memoization is a core technique used in many algorithms and is extremely common in interviews. But now, let's pause for a moment and ask an important question. Do we really need to use recursion here? Can we solve this problem with a loop? If you think about it, it really looks like we're naturally moving through the steps in order. We start with the first step and compute the number of paths. Then we move to the second step and do the same. Then for the third step, we already have everything we need, so we can just apply the formula. And then we keep going like that. In other words, it seems we can simply move from one step to the next in a loop. We already know the formula, but for this to work, we need to store the results of the previous steps somewhere. And the simplest option is an array. Each index in the array would represent a step number. And inside that cell, we store the number of ways to reach that step. Then we just move forward along the staircase in a loop. Take the last two values, apply the formula, and store the result in the next cell. And we repeat this until we reach the final step. And there's no recursion here, no cache checks, no call stack, just a clean bottom-up loop where every step depends only on the previous two results. Let's walk through how this works step by step using the example with five steps. First, we create an array and immediately fill in the base cases. At index one, which is step one, we store one path. At index two, which is step two, we store two paths. Now, we move forward. For step three, we look at step two and step one and add those values together. 1 + 2 gives us three. So, we store that in the third cell. Then for step four, we take the value from step three, which is three, and add the value from step two, which is two. That gives us five. So we store it. And then for step five, we take the value from step four, which is five, and add the value from step three, which is three. That gives us eight. And we store it, too. And that's it. The answer is now sitting in the last cell of the array. Now, let's summarize what this solution does conceptually. First, we create an array, a table, where we store already made answers for each step from bottom to top. For steps one and two, we immediately write down the known base cases. Then we run a simple loop starting from the third step and moving upward. On each iteration, we take the two previous values from the array, add them together, and write the result into the current position. And at the very end, we return the last value in the array. That's the number of ways to reach the required step. This loop-based approach also has a name, tabulation. Tabulation is a technique where we explicitly fill a table of results step by step. first the base cases and then gradually build up to the final answer using previously computed values. It's one of the fundamental and very powerful techniques that appear in a huge number of problems. It gives predictable performance, avoids recursion entirely and has linear time complexity and the memory usage is also O of N since we store one value per step. Now let's compare these two approaches. The main difference is simple. Memorization is recursion with memory. We solve the problem top down and store intermediate results in a cache. Tabulation on the other hand is a bottom up loop. We fill an array step by step from the start all the way to the final answer. There's also a difference in how memory is used. Memorization needs memory for the cache and for the recursion call stack whereas tabulation only needs the array which usually makes it more efficient. So which approach should you choose in a real problem? If you're working on a problem where the order of computations doesn't really matter, a top- down approach is often a great fit, recursion naturally computes all the intermediate values you need, and you don't have to think too hard about the order yourself. This works especially well for partition type problems. For example, when you need to split a string into parts or divide an array into groups. In those cases, recursion with memorization is very convenient because it automatically explores and computes all the inner partitions. With a bottomup approach in problems like that, it's often not obvious which partitions should be computed first in order to calculate the rest. Figuring out that order can make the solution much harder. On the other hand, when you use a bottomup approach, it's usually easier to analyze the time complexity. You can clearly see the cost of filling the table of intermediate results and loops tend to make this more visible than recursion. There's another important benefit as well. With a bottomup solution, you never risk a stack overflow because there's no recursion involved. So if you can clearly see an order in which intermediate results can be computed one by one, bottom up is usually the best choice. But if the order is unclear or hard to reason about, top down is often the better option to start. Now let's apply this comparison to our staircase example. Here we need all steps from one up to the final one. There are no unnecessary sub problems. And we also know the exact order in which everything should be computed bottom up. And the code itself is much simpler too. just a loop instead of recursive calls and checks. So for this staircase problem, tabulation really wins on all fronts. Memoization is great when recursion fits naturally or when not all sub problems are needed. But here we have a clean sequence, a classic case for tabulation. We fill the table once from bottom to top and we're done. Fast, simple, no extra checks. That said, if you personally find the recursive solution easier to understand or to come up with, it's completely fine to use that approach in an interview. Now, let's practice on the Algo Monster platform and solve one more popular problem using the techniques we've just learned. It's called the nth Fibonacci number. And basically, it's an extension of a classical Fibonacci sequence problem where each next number in the sequence is the sum of two previous numbers. But here in the Fibonacci problem, each next number is the sum of not two but three previous numbers. So, to get the nth number in the sequence, you'd need to add numbers n minus1, nus2, and n minus3 together. And the Fibonacci sequence always starts from these three numbers. The zero element is zero. The first is one and the second is also one. So given the nth triaci element number, we need to find its value. For example, if n equals 3, we just use this formula adding all the previous three elements, the second, the first, and the zeroth. They're given in the problem statement. So we'd get two in total. And this is the answer for n= 3. But if n equals 4, then we'd need to add the third, the second, and the first elements. Now looking at their values, we'd get four in total. And in general, we need to write the code that returns the answer for any n. And this problem looks quite similar to our staircase problem. We even have the formula here where it's clear that every next element depends on the previous ones. So to find the nth element, we first need to find those three. And we could do that using any approach we've learned. We could find it recursively, for example, and use memorization to optimize it. Or just like here, we could create an array of n elements, store the first three as they're given, and then move left to right, calculating each next element using the formula we have. Classic bottom-up approach. However, just like in the staircase problem, we see that each next element depends on only three previous ones. So on each step, we don't need elements before those three. And that means we don't need to store an entire array. We can just have three variables storing the values of the previous elements and update them on each next step. We'd initialize them with the first numbers in the sequence, 0, 1, and one. And then we'd use the formula to calculate the next number. After that's done, we'd update the variables so they contain the last three elements in the sequence, 1, 1, and two, because we've just found a new one. And then we do the same until we reach the nth element in the loop. With this approach, we'd need to start from the first elements of the sequence and move all the way to the nth element to calculate it eventually. That means we have O of N time complexity. But for the space, we always store just three variables, never more. That means our memory usage is constant, giving us O of one space complexity. This is the optimal solution for this problem. Let's write the code for it. We have a function that takes one argument N, the Fibonacci number we need to return. First, we have our base cases. From the problem statement, we know that the zero element is always zero. So, we can write them. Besides, we know that the first and the second elements in the sequence are ones. So we can add this base case too. Then if we got a bigger n, we need to use our formula to calculate its value. Following our approach, we create three variables and initialize them with the values of the first three elements in the sequence 0 1 and 1. Then we need to calculate each next element in sequence using our formula until we reach the nth position. For that we can start a loop from the third position until n +1. Inside we just use our formula to calculate the next element based on the three previous ones. But then we need to update our variables so we can calculate the next elements later. For that it's convenient to use tpple assignment in Python. Basically we say here that t0 gets the value of t1. T1 becomes t2 and t2 becomes the result of our formula. After the loop completes the t2 variable will contain the nth element value because we save the result of the formula in this variable on every iteration. So we just return this value and this is our solution. Let's run the test to see if we solved it correctly. and it's perfect. There are plenty of other problems and their solutions available on the Algo Monster platform. Click the link in the description to practice and easily prep for your coding interviews. Okay, so we figured out how many ways there are to climb to the nth step. But now let's change the problem slightly. What if every step costs money and instead of just reaching the top, you want to do it for the minimum possible price? This leads us to a very popular problem called minost climbing stairs. and you'll see that it's solved in almost the same way as the problem we just looked at. In this problem, you're given an array called cost. Each element in this array represents the price you pay when you land on a particular stair. Land on stair one, you pay that amount. Land on stair two, you pay that amount, and so on. You're allowed to start climbing from either stair zero or stair one. From any stair, you can move up to the next stair or jump over one stair. Just like in the previous problem, but now the goal is slightly different. You don't just want to reach a stair. You want to reach the very top of the staircase, the floor, and you want to do it with the minimum possible cost. So, the task is to find the minimum cost needed to climb all the way to the top. Let's look at a simple example. Suppose we have three stairs. Stair 0 cost 10, stair 1 costs 15, and stair 2 costs 20. That's our cost array. Your goal is to end up at the very top. In other words, to reach the floor. The floor itself is not part of the array because it's no longer a stair. So, what options do we have? One option is to start from stair zero and pay 10. From there, you jump over one stair and land directly on stair 2, paying 20. Then you take one more step and reach the floor. The total cost of this path is 10 + 20, which gives us 30. Another option is to start from stair 1 and pay 15. From there, you jump over one stair and immediately reach the floor. This path costs just 15. And that's the answer to our problem because we're looking for the minimum possible cost. There are a few other possible paths here as well, but all of them end up being more expensive. So, in this case, 15 is the best cost we can get. One important thing to notice here is this. We do not pay for landing on the floor. We only pay for the stairs we land on inside the array. Let's recall how we previously counted the number of ways to reach stair n. We said that you can reach stair n either from stair n minus one or from stair n minus 2. So ways of n equals ways n minus1 plus ways n minus2. Now the goal is different. We no longer care about the number of ways. We care about the minimum cost. But here's the key point. The transition logic stays exactly the same. You can still reach stair n in only two ways. Either from stair n minus one by taking one step or from stair n minus2 by jumping over one stair. So structurally nothing changes. The only real question now is this. How do we choose the cheaper of these two options? It turns out that just like in the previous problem, we can create an array where we store an intermediate value for each stair. The difference is that before we were storing the number of ways and now we're going to store the minimum cost to reach each stair. Let's call this array minost. Why do we need it? Because in this problem, once again, every next result depends on the previous ones. You can only reach a stair from lower stairs, which means we first need to know the minimum costs of those lower stairs. So once again, we need a place to store previously computed results. An array fits perfectly here. The index represents the stair number and the value represents the minimum cost to reach that stair. Why does this work? Because we already know the minimum cost for stair zero. It's just its own price since that's where we start. So we can put in the array straight away. It's a base case. The same goes for stair one because we're allowed to start there directly as well. So its value can also be written into the min cost array right away. Now we can compute the minimum cost for stair 2. Watch closely. We know that we can come to it only from stair 1 or from stair zero. These are the only two possible options. But we need to minimize the cost to the top. So which of these two options do we choose to get to the stair two? Well, the cheapest one. We just look at these two costs and choose the minimum of those. But then because we jump on the stair two now we need to add it two to the total. Its price is known from the cost array. So we just add it to the minimal cost we chose from the previous two options. And it gives us the minimal cost to get to the stair 2. So we store it in the array. Then we do the same for stair three. Its cost is known and the minimum costs for the previous stairs are already computed. We choose the minimal one, add the stair cost, and we get the total minimal cost for stair 3. And then step by step, always relying on values we've already computed, we calculate the minimum cost for every stair and store it in our array for future use. This is the classic bottomup approach. We start with the base values and gradually build up to the final result. As a result, we end up with the minost array that makes solving the problem straightforward. We simply take the minimum cost from the last two stairs because from either of them we can reach the floor. This is very similar to the previous problem and that's exactly the power of recognizing patterns. Let's generalize the approach. Let minost n be the minimum total cost needed to step onto stair n starting from the beginning. Now where could you have come from to reach stair n? You could come from stair n minus one. In that case you've already paid the minimum total cost to reach stair n minus one. Or you could come from stair n minus2. Then you've already paid the minimum total cost to reach stair n minus2. Which option is better? The cheaper one. So we take the minimum of those two values and then we also add the cost to reach the stair n from the original array of costs. Now that we figured everything out conceptually, let's translate this idea into an actual solution. We start by defining a function. As input, it receives the cost array which contains the prices for each stair. This is exactly what the problem gives us. For convenience, we first store the length of this array. This tells us how many stairs there are in total. Next, we create the minost array. This is where we'll store the minimum total cost required to reach each stair. Now come the base cases. Just like we discussed earlier, the minimum cost to reach stair zero is simply its own price. After all, we're allowed to start by stepping on it directly. The same idea applies to stair 1. So, its price can also be written into the array right away. After that, we compute the remaining values. We go through the stairs starting from stair two and move forward one stair at a time. For each stair, we apply our formula. We take the cost of stepping on the current stair and add the smaller of the minimum costs for the two previous stairs. As the loop runs, it computes the minimum cost for stair 2, then for stair three, and so on until the entire minost array is filled. Each new value depends only on the two values before it. Once we're done, the last two cells in the min cost array contain the minimum cost of stepping on the last two stairs. And those are exactly the stairs from which we can jump to the top floor. So to get the final answer, we simply take the smaller of those two values. And that's our solution. Now let's evaluate the complexity of the solution. First, the time complexity. We run a single loop that starts at stair 2 and goes up to the last stair. That's a straight linear pass. So the time complexity is O of N. Now the space complexity. We create the minost array and it has exactly as many cells as there are stairs. Because of that, the space complexity is also O of N. That's already pretty good. But we could actually make this algorithm even more efficient. Let's take a closer look and see where there's still some inefficiency. Look carefully at the formula we use inside the loop. To compute the minimum cost for stair n, we only need two values. The minimum costs for stairs n minus one and n minus2. That's it. We don't need all the previous values. We don't need half of the array. We need exactly two numbers. And think about what happens to mimos zero once we get to say stair five. Nothing at all. We used it long ago and after that it never comes up again. So what's really happening here is this. We're storing a whole array of values but in practice at any moment we're only using the last two which leads to an obvious question. If we only ever need two values, why are we storing the entire array? So what if we remove the array entirely and use just two variables instead? One variable will store the minimum cost to reach the previous stair and the other will store the minimum cost to reach the stair before that. We initialize these two variables in exactly the same way as before using the cost of stair zero and stair 1. Then we start moving forward through the staircase. Inside the loop, we compute the new value using the same formula as before. The only difference is that now we're taking the previous values directly from our two variables instead of reading them from an array. And after computing the new minimum cost, we update the variables. The first variable takes the value of the second one and the second variable takes the new cost we just calculated. This way, at every moment, we're keeping track of the last two stairs we've reached. And those are the only values we ever need. Once we're done, we return the minimum of these two values exactly like before. Because from either of those stairs, we can reach the floor. And the time complexity of this solution stays exactly the same. O of N. We still have a single loop that goes through the stairs. But the space complexity is now different. Instead of storing a whole array, we only use two variables. That means the space complexity drops to O of 1, constant space. So we reduced memory usage from O of N to O of 1 without losing any speed. That's exactly what we want. But now let's step back and see when this solution logic applies in general because that's the second problem already which we solved similarly. Look at what this problem and the earlier number of ways problem have in common. First, the state depends on a fixed number of previous states. In our case, it's just two n minus one and n minus2. Second, the transition is always the same. It doesn't matter which stair you're on. The formula never changes. And third, the memory can be optimized. Since we only ever need the last two values, there's no reason to store the entire array. This is what we call a constant transition. A transition that depends on a constant number of previous states. It's one of the fundamental patterns in dynamic programming. And as you've just seen, very different problems can often be solved in almost the same way. The formulas may look slightly different, but the underlying logic is exactly the same. That's the real power of patterns. You don't need to memorize solutions to every problem out there. If you understand just a handful of core patterns, you can solve a huge range of problems. And next, we'll go through five more key patterns just as simply and clearly as this one. So, keep watching. But first, let's go to Algo Monster and solve a very popular constant transition problem. It's called House Robber. And here we're playing the role of a robber who plans to rob houses along a street. Each house has a certain amount of treasure in it, but the constraint is that we cannot rob two adjacent houses. So, we need to figure out the maximum amount of money we can get from those houses without breaking this constraint. Here, we're given an array of integers representing the amount of money of each house. And basically, we need to maximize the sum of non-adjacent elements. The phrase maximize the sum is already assigned that this is a DP problem. But here we need to figure out the formula ourselves. How do we do that? So what if we create an additional array where in each cell we will store the maximum sum we can get if we rob all the houses from the first to the current one. Then for the first one we just store its value because there are no houses before that. And for the second we choose the maximum between it and the previous house because if the previous one is better then we cannot rob the adjacent one or vice versa. So we take the best option possible here. These are base cases. But then when we move further along the street and look at any house deciding if we need to rob it or not, we also have only two options. Break into that one or skip it because an adjacent one may be better. So if we're currently looking at the third house with the value of nine, then we could skip it and bear the same sum we had in the previous cell, which is seven. Or we could rob the one before that and now rob the current one, too. Which is better? The maximum one. 2 + 9 gives us 11. So we definitely want to use that one. And moving along, we have the same choice. Use just the previous one or the one before that plus the current. And then we just take the maximum of these two options. So that's basically our formula. We're choosing from the two previous sums, but add the current element to the non-adjacent one. Then in the last element of our array, we'll eventually have the maximum sum of all the houses. And this is our answer. If we solve it exactly this way, then we'd need to create an array of n elements, which would give us O of N space complexity. And then we'd go over all the elements from 0 to n which also has O of N time complexity. However, we can again optimize the approach and use just two variables to store the last two sums as those are the only ones used in the formula. That would allow us to have O of one space complexity. So let's implement this solution. I'll save the length of the houses array in the variable N for convenience. Then we need to cover a couple of base cases. If the array length is zero, then the answer is obviously 02. Or if there are only one or two houses in the array, we can just choose the maximum element because there are no other combinations. For any other array, we need to implement our algorithm. First, the DP base cases. We save the value of the first house in the array and we take the maximum of the first two houses and save it in a variable 2. That's the values we'll start calculating the next sums from. Then we need to go over the rest of the houses. So, we start a loop from index 2 till the array length. And inside we just apply our formula and change the variable values for the next iteration. In the end, the second variable contains the final sum which we return from the function. Now let's run the test to check if our solution is correct. And that works. Awesome. You can solve this problem yourself if you want. Just click the link in the description. Okay. So we've learned how to climb a staircase. We counted paths and we counted costs. But there was one important limitation. We were always moving in just one direction. Upward. one stair or two, but never anything else. So, what happens if we're allowed to move in more than one direction? And what if instead of a staircase, we're dealing with an entire grid? This brings us to the next dynamic programming pattern, and you'll see that it's solved in a very similar way to everything we've already learned. Here's a grid, a regular table made up of cells. It has m rows and n columns. You start in the top left corner, and your goal is to reach the bottom right corner. There's just one rule. You can move only to the right or downward. No moving left and no moving up. So the question is simple. How many unique paths are there from the start to the finish? This is a very popular problem called unique paths. And it should already sound familiar. In our first staircase problem, we were also counting the number of paths. So now with that experience, this one will be much easier to understand. Let's look at a simple example. A 3x3 grid. That gives us nine cells in total. We start in the top left corner and want to reach the bottom right corner. So, what options do we have? One option is to go all the way to the right first and then all the way down. That's one path. Another option is to go all the way down first and then all the way to the right. That's a second path. Or we can alternate our moves. Right, down, right, down. That gives us a third path. And there are several other combinations like this. In fact, for a 3x3 grid, there are exactly six unique paths. But now comes the real question. How do we count this for any grid? for a 5x5 grid or for a 10x10 grid. Clearly brute forcing all possibilities by hand isn't an option. We need a proper algorithm. Now look closely and think back to the staircase problem. There we said that you can reach stair n either from n minus one or from n minus2. And here what about a cell in the grid? From where can you reach it? Either from the cell on the left if you move right or from the cell above if you move down. There are no other possibilities. The rules of the problem simply don't allow anything else. So the logic is exactly the same. The number of paths to the current cell is equal to the sum of the number of paths to the neighboring cells from which you can reach it. If you've already reached those neighboring cells in different ways, you just continue those paths to arrive at the current cell. Then you add all those possibilities together and that's your result. The only real difference is this. Instead of steps from the previous problem, we now have two neighboring cells. The one on the left and the one above. For this problem, it would be very helpful to have a table where for each cell, we store the number of paths that lead to it. Then the solution becomes simple. We take the two neighboring cells, add their values, and get the answer. It's very similar to the staircase problem, but since we're working with a grid now, we need a table to remember the number of paths for each cell. Of course, the problem doesn't give us such a table, but that's fine. We can build it ourselves step by step. Let's start with the simplest part. How many paths are there to the starting cell? Just one. You're already standing there. Now, let's look at the first row. How can you reach any cell in this row? Only from the cell on the left. There's nothing above it. That's the edge of the grid. And coming from below isn't allowed by the rules. So, there's exactly one path to every cell in the first row. You just keep moving to the right. The same idea applies to the first column, the leftmost one. How can you reach any of its cells? Only from the cell above. There's nothing on the left, again, the edge of the grid. And coming from the right isn't allowed either. So there's exactly one path to every cell in the first column as well. You just keep moving downward. Now move to the next cell to this one. We could come from the left cell and there is one path to that one already. Or we could come from above and there's one path to that one. So we add them together and get two total paths to this cell. And this pattern continues. In general, we can write the formula like this. The number of paths to the current cell is the number of paths to the cell above it plus the number of paths to the cell on the left. Now all that's left is to fill the grid using this formula row by row or column by column. The important thing is to move in an order where the needed neighboring cells have already been computed. At the end, we simply look at the bottom right cell in our table. That's where the answer is stored. Clean, elegant, and most importantly, very similar to everything we already know. Now that the logic is clear, let's turn it into an actual solution. We start by creating an empty table called paths. This is just a two-dimensional array. It has m rows and n columns. Exactly the same shape as our grid. First, we fill the top row with ones. As we already discussed, there's exactly one path to every cell in the first row. Next, we fill the first column with ones as well. For the same reason, there's exactly one path to every cell in the leftmost column. And now we can compute all the remaining cells. So, we go row by row starting from the second row. We don't start from the very first one because the top row is already filled. And inside that loop we go column by column also starting from the second column since the leftmost column is already handled. Together these two loops walk through every remaining cell in the grid. And for each cell we apply the same rule we derived earlier. We take the number of paths from the cell above. Take the number of paths from the cell on the left and add them together. Then step by step the table gets filled with the correct values. And by the time we finish every cell contains the number of unique paths that lead to it. And since our goal is to reach the bottom right corner, we simply look at that cell in the table. That value is the answer. Clean, systematic, and very familiar by now. Exactly what we expect from dynamic programming. Now, let's evaluate the complexity of this algorithm. First, the time complexity. Here we have two nested loops. The outer loop runs m times, once for each row. Inside it, the inner loop runs m times once for each column. Together, that gives us O of M * N, linear in the total number of cells. Now the space complexity we create and store a table with m rows and n columns. So the space complexity is also O of M * N. That's already quite good. But just like in the previous problem, you might notice that we can optimize this even further. Let's look at the formula one more time. To compute the values for the current row, we only need two things. The previous row because we're taking an element from above and the current row that we're filling right now because we're taking an element from the left. All other rows above are no longer useful. We've already used them and we'll never need them again. So, keeping the entire table in memory is wasteful. In fact, a single row is enough. Then, let's optimize the solution with that idea in mind. First, we create a one-dimensional array called row with length n and immediately fill it with ones. This represents the first row of the grid where there's exactly one path to each cell. Now, we iterate over the remaining rows of the grid starting from the second one. Inside that, we go through each column. For every cell, we update the value in the current row using the same formula as before. But here's the key insight. Row J still holds the value from the cell above because it hasn't been updated yet in this iteration. Row J minus one already holds the value from the cell on the left because we just updated it. So by adding these two values together, we get the correct number of paths for the current cell. The important trick here is that instead of writing results into a new row, we overwrite values in the same array. That's safe because once we move forward, we no longer need the old values. By the time we finish processing all rows and columns, the last element in this array contains the answer, the number of unique paths to the bottom right cell. And for this solution, the time complexity stays the same, O of M * N, since we still use two nested loops. But the space complexity is now much better. we only store one row. So it drops to O of N instead of O of M * N. And if M happens to be larger than M, we could just as easily store a column instead of a row. In that case, the space complexity becomes O of min of M and N. The idea stays exactly the same. We just keep the minimum amount of data we actually need. Now let's summarize the typical signs of a grid problem. First, you're working with a two-dimensional space, a table, a grid, a matrix, something with two dimensions. Second, movement is restricted. In many of these problems, you can move only to the right and downward. Sometimes other directions are allowed as well, but the number of possible moves is usually limited. Third, the state of each cell depends on its neighboring cells, specifically the cells you're allowed to come from. In this problem, for example, you can reach a cell only from above or from the left. Fourth, there are clear base cases, the edges of the grid, and those can be filled in immediately. So, if you see a problem like this, the strategy is straightforward. Build a table, fill in the borders, and then compute the remaining cells using a formula derived from the movement rules. That's the grid pattern, two-dimensional dynamic programming. Now, let's practice with the grid pattern and solve a variation of the previous problem on Algo Monster. It's called unique paths 2. We also have a grid here, and we're located at its top left corner. And we need to find the number of unique paths to the bottom right corner, just as in the previous problem. And again, we can move either down or right. However, now there can be obstacles in the grid where we cannot move. So, our grid consists of integer numbers, zeros and ones. If a cell has zero as its value, we can move there. If it's one, this cell is blocked and we need to find another way around it. Well, how do we find all the unique paths here? We already know the logic and the formula for finding the paths from the previous problem. We just build a grid and for each cell, store a sum of the two adjacent cells, the left one and the top one. However, now we have the cells where we cannot move. What does that mean for our DP grid? It means that there are no ways at all to any cell that has an obstacle inside it. So when we meet such cell, we just put zero in it inside our DP grid. And for others, we use the same formula we had before. But here we can optimize the solution again if we create not a whole DP grid, but a one-dimensional array that stores just one row of this grid we're processing. Just because we never use any other cells except the adjacent ones. With such a solution, we'd still go over all the cells of the initial grid, which would give us O of M * N time complexity. But we'd have just O of N space complexity. As we store only one row of this grid throughout the solution. Let's write the code for this solution. First of all, if our starting cell has an obstacle inside it, we can just return zero as there are no ways out of it. Then I'll create variables M and N for the number of rows and columns in the grid just for convenience. Now we create our DP array of N elements where we will be calculating our unique paths to every cell of the grid. The leftmost element of this array is one just because there's only one path to the cell where we're starting. Then we'd need to go over all the elements in the grid. For that we create two loops by rows and by columns. And inside we first check if we came across an obstacle. In other words, the current cell contains one inside. If that's true, then we just put zero in our DP array as there are no ways at all to the cell that has an obstacle inside. Otherwise, we just add the number