Learn Dynamic Programming with Animations – Full Course for Beginners

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

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

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

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

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.

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.

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

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

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

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

difficult. So it's better to write code that quickly calculates all possible paths. Where do we start? Let's think

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

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

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

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

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

new. Now let's see what happens with step four. Here the same logic of

step four. Here the same logic of extending existing paths applies again.

First option, we reach step four through step three. Everything we already

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

four. These are not new paths, just the same routes extended to the top of the staircase. And the second option, we

staircase. And the second option, we jump directly from step two to step four. For step two, we already have two

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

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

two. Total five ways. So the idea is this. We only count distinct routes for

this. We only count distinct routes for the two previous steps and then extend them. The same path can never be counted

them. The same path can never be counted twice. We only expand it by one more

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

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

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

possible ways. Either two small steps or one big jump. This is our second base case. And for all other steps, we use

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

two numbers? This is where recursion comes in. The function simply calls

comes in. The function simply calls itself. First it asks how many ways are

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

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

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

two checks. 3 is neither equal to 1 nor to two. So we move on to the formula to

to two. So we move on to the formula to compute the number of ways to reach step three. The function first calls itself

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

both numbers. So we simply add them together. 2 + 1 gives us three. And

together. 2 + 1 gives us three. And

that's exactly the value the function returns. Everything checks out. Now

returns. Everything checks out. Now

let's go one step further and look at step four. If n= 4, the function again

step four. If n= 4, the function again follows the same logic just one level deeper. First it calls itself for step

deeper. First it calls itself for step three. Inside that call, the function

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

two. Now, we can apply the formula for step 4. 3 + 2. So, the result is five

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

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

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

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

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

somewhere? Then every next time we need it, we can just reuse it instead of recmputing everything. If we want to

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

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

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

step three. Once again, nothing is stored yet. So, we need the values for

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

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

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

three. We add the values together, get the result. But now before returning, we

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

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

case. We add the two values, store the result for step four in the hashmap and return it. And now comes the best part.

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

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

conceptually. First, we create an empty storage, a hashmap, where we'll keep all computed results. Then inside the

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

before. If those don't apply, we compute the number of ways recursively using our formula. But now there's one extra step.

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

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

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

with memory. We still solve the problem top down, but every answer we discover gets saved. So future calls can just

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

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

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

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

the formula. And then we keep going like that. In other words, it seems we can

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

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

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

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

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,

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.

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

three. That gives us eight. And we store it, too. And that's it. The answer is

it, too. And that's it. The answer is now sitting in the last cell of the array. Now, let's summarize what this

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

cases. Then we run a simple loop starting from the third step and moving upward. On each iteration, we take the

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

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

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

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

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

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

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

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

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

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,

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

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

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

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

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

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

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

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

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

them. Besides, we know that the first and the second elements in the sequence are ones. So we can add this base case

are ones. So we can add this base case too. Then if we got a bigger n, we need

too. Then if we got a bigger n, we need to use our formula to calculate its value. Following our approach, we create

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

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

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

interviews. Okay, so we figured out how many ways there are to climb to the nth step. But now let's change the problem

step. But now let's change the problem slightly. What if every step costs money

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

possible price? This leads us to a very popular problem called minost climbing stairs. and you'll see that it's solved

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

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

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

15. And that's the answer to our problem because we're looking for the minimum possible cost. There are a few other

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

get. One important thing to notice here is this. We do not pay for landing on

is this. We do not pay for landing on the floor. We only pay for the stairs we

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

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

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

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

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

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

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

array. Then we do the same for stair three. Its cost is known and the minimum

three. Its cost is known and the minimum costs for the previous stairs are already computed. We choose the minimal

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.

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

minus one. Or you could come from stair n minus2. Then you've already paid the

n minus2. Then you've already paid the minimum total cost to reach stair n minus2. Which option is better? The

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

solution. We start by defining a function. As input, it receives the cost

function. As input, it receives the cost array which contains the prices for each stair. This is exactly what the problem

stair. This is exactly what the problem gives us. For convenience, we first

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.

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

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

away. After that, we compute the remaining values. We go through 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

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.

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

N. That's already pretty good. But we

could actually make this algorithm even more efficient. Let's take a closer look

more efficient. Let's take a closer look and see where there's still some inefficiency. Look carefully at the

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

previous values. We don't need half of the array. We need exactly two numbers.

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

obvious question. If we only ever need two values, why are we storing the entire array? So what if we remove the

entire array? So what if we remove the array entirely and use just two variables instead? One variable will

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

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

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

stairs. But the space complexity is now different. Instead of storing a whole

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

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

similarly. Look at what this problem and the earlier number of ways problem have in common. First, the state depends on a

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

minus2. Second, the transition is always the same. It doesn't matter which stair

the same. It doesn't matter which stair you're on. The formula never changes.

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

entire array. This is what we call a constant transition. A transition that

constant transition. A transition that depends on a constant number of previous states. It's one of the fundamental

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

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

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

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

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

vice versa. So we take the best option possible here. These are base cases. But

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

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

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

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

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

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

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

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

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

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

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

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

direction? And what if instead of a staircase, we're dealing with an entire grid? This brings us to the next dynamic

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

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

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

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

to understand. Let's look at a simple example. A 3x3 grid. That gives us nine

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

right corner. So, what options do we have? One option is to go all the way to

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

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

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

question. How do we count this for any grid? for a 5x5 grid or for a 10x10

grid? for a 5x5 grid or for a 10x10 grid. Clearly brute forcing all

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

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

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

other possibilities. The rules of the problem simply don't allow anything else. So the logic is exactly the same.

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

cell. Then you add all those possibilities together and that's your result. The only real difference is

result. The only real difference is this. Instead of steps from the previous

this. Instead of steps from the previous problem, we now have two neighboring cells. The one on the left and the one

cells. The one on the left and the one above. For this problem, it would be

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

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

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

cell? Just one. You're already standing there. Now, let's look at the first row.

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

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

first row. You just keep moving to the right. The same idea applies 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

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

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 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

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

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

paths. This is just a two-dimensional array. It has m rows and n columns.

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

as well. For the same reason, there's exactly one path to every cell in the leftmost column. And now we can compute

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

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

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

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.

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

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

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

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

same array. That's safe because once we move forward, we no longer need the old values. By the time we finish processing

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

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

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.

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

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,

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

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

Algo Monster. It's called unique paths 2. We also have a grid here, and we're

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

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

it. Well, how do we find all the unique paths here? We already know the logic

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

processing. Just because we never use any other cells except the adjacent ones. With such a solution, we'd still

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

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. Let's write the code for this solution. First of all, if our starting

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

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

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

obstacle inside. Otherwise, we just add the number of unique paths to the cell on the left from the current, which is DPJ minus one to the number of unique paths to the cell on top of the current.

This one is being stored in DPJ from the previous iterations. So, we just use its

previous iterations. So, we just use its value and save the new result to the same cell. In the end, the last element

same cell. In the end, the last element of our DP array has our final answer as it corresponds to the bottom right corner of the grid. So, we return it.

Let's run the test and check if we solved it correctly. Works good. So,

another problem is tackled. If you want to solve it yourself, click the link in the description of this video. Okay,

we've learned how to work with grids.

There was a table and we filled it cell by cell. But there are also problems

by cell. But there are also problems where you can still use a grid-like idea to solve them, even though a grid is not explicitly mentioned in the problem description. For example, this happens

description. For example, this happens when you're given two strings and need to compare them with each other. This

brings us to the next dynamic programming pattern, two sequences. And

now you'll see that it is also solved using a two-dimensional table. The

structure is the same, but the logic for filling the table is a bit different.

Here is a very popular problem, longest common subsequence. You are given two

common subsequence. You are given two strings and you need to find the length of their longest common subsequence. But

before we go further, let's clarify what a subsequence actually is. It is not a substring. A substring means that the

substring. A substring means that the characters go one after another without any gaps. A subsequence on the other

any gaps. A subsequence on the other hand means that the characters appear in the same order but there may be gaps between them. Take the word stone as an

between them. Take the word stone as an example. Ton is a substring. Three

example. Ton is a substring. Three

consecutive characters but toe is a subsequence. We skip the N but the order

subsequence. We skip the N but the order is still preserved. First T, then O, then E. So the task is to find the

then E. So the task is to find the longest such subsequence that exists in both strings at the same time. Let's

take two words stone and tower. What

common subsequences do we have here? The

letter T appears in both words. So

that's a subsequence of length one. The

letters T and O also appear in both words and in the same order. So that's a subsequence of length two. What about T, O, and E? All three appear in the first

word, and all three appear in the second word. The order matches. So toe is a

word. The order matches. So toe is a common subsequence of length three. Can

we find anything longer? Let's check.

The letters S and N from the first word don't appear in the second. And the

letters W and R from the second word don't appear in the first. So the answer is three. Toe is the longest common

is three. Toe is the longest common subsequence for these two words. Okay.

So how could we solve this problem directly? One idea is to take the first

directly? One idea is to take the first string and generate all of its possible subsequences. Then for each of them

subsequences. Then for each of them check whether it appears in the second string and finally choose the longest one that does. But here's the problem.

How many subsequences does a string of length n have? For each character, you have two choices. Either include it or skip it. So for n characters, you get 2

skip it. So for n characters, you get 2 to the^ of n subsequences. If n is 10, that's 1,024.

Still manageable. If n is 20, that's already about a million. If n is 30, that's a billion. And in this problem, strings can be up to 1,000 characters long. That's 2 to the power of 1,000

long. That's 2 to the power of 1,000 possibilities, a number with hundreds of digits. The universe will end long

digits. The universe will end long before our program finishes. So clearly,

we need a smarter approach. In previous

problems, we built a table and filled it step by step. So maybe we can do the same thing here. Remember the grid problem? There we already had a table,

problem? There we already had a table, the grid, and we just filled it with values. We had a vertical position and a

values. We had a vertical position and a horizontal position. And for each cell,

horizontal position. And for each cell, we computed the answer step by step.

Here we don't have any table yet. We

only have two strings, stone and tower.

So the natural question is where do we even get a table from? Look, to solve this problem, we need to somehow compare these strings, not as a whole, but in parts because a subsequence is about

which characters we take and which ones we skip along the way. That means it's important to know which character of the first string we're currently at, and also which character of the second string we're at. So now we have two

positions, a position in the first string, let's call it I, and a position in the second string, J. Let's take our strings stone and tower. Suppose I

equals 1. That means we're looking only at the first character of the first string S. And J equals 1. That means

string S. And J equals 1. That means

we're looking only at the first character of the second string T. What

is the longest common subsequence for S and T? None. The letters are different,

and T? None. The letters are different, so the answer is zero. Next, J equals 2 and we compare S and to. There is no S there, so the answer is still zero. And

as we go further, S doesn't appear anywhere in the second string. So we

just keep putting zeros. Now I equals 2 and we take ST from the first string. We

compare ST and T. There is a common T.

So the answer is one. Then we compare ST and TO. The only common letter is still

and TO. The only common letter is still T. So the answer stays one. And for all

T. So the answer stays one. And for all the other variants, only T matches in ST. So we put one everywhere. Now the

ST. So we put one everywhere. Now the

third row, we take ST. For J equals 1, we compare ST and T. There is a common T. So the answer is one. Then we compare

T. So the answer is one. Then we compare S T and T to O. Here we have both T and O and they are in the correct order. So

the answer is already two. All other

variants won't add anything new beyond to. So we put two everywhere. See, we're

to. So we put two everywhere. See, we're

literally filling a table again. We've

just built it ourselves. The position in the first string goes along the vertical axis. The position in the second string

axis. The position in the second string goes along the horizontal axis. And each

cell contains the answer for those specific positions. And if we fill the

specific positions. And if we fill the whole table all the way to the end, then in the bottom right corner, we'll get the answer for the full strings. That is

the solution to our problem. But filling

each cell by hand would be way too slow.

So once again, we need a formula that lets us compute the value of any cell based on values we've already computed.

Let's call our strings first and second.

Then we'll create a table dp of size m + 1 by m + 1, where m is the length of the first string and n is the length of the second. Why + 1? Because we need a base

second. Why + 1? Because we need a base case, the empty string. If one of the strings is empty, what is their common subsequence? None. The length is zero.

subsequence? None. The length is zero.

So the first row of the table is all zeros and the first column is also all zeros. Now comes the interesting part.

zeros. Now comes the interesting part.

How do we fill the remaining cells? What

does DPI J represent? It represents the length of the longest common subsequence for the first I characters of the first string and the first J characters of the

second string. Imagine we're standing at

second string. Imagine we're standing at the cell DPI J and we're looking at the corresponding characters in both strings. And now we have two possible

strings. And now we have two possible cases. First case, the characters match.

cases. First case, the characters match.

Suppose we compare ST to O and to O. The

last letters are O and O. They are the same. That means this letter will

same. That means this letter will definitely be part of our common subsequence because it exists in both strings at the current positions. So

what was the longest common subsequence before this character? That would be for ST and T without the last letters. This

is exactly the cell DPI -1 JUS1 the diagonal one and it contains one because ST and T share the letter T. Since we've

now found another common letter O, we just add one to what we already had. So

we get 1 + 1 equals 2. In other words, to compute the current cell, we take the diagonal cell and add one to it. Why the

diagonal? Because we're consuming one character from each string. They match.

So both are included in the subsequence.

That's why we look at the cell where both strings are shorter by one character and then increase that result by one. Now the second case, the

by one. Now the second case, the characters are different. Suppose we

compare s and to o w. The last letters are o and w. They're different, so they cannot both be part of the common subsequence. So which result do we take?

subsequence. So which result do we take?

We can skip the last character of the first string and look at the result for st and to w. That's the cell dp i minus1 j one row above. Or we can skip the last

character of the second string and look at the result for ST and TO. That's the

cell DPI J minus one, one column to the left. We don't know which choice is

left. We don't know which choice is better ahead of time, so we take the maximum of the two. We want the longest subsequence possible. In the end, we

subsequence possible. In the end, we simply choose which formula to apply based on whether the current characters match or not. Now, let's see how all of this works. Step by step, we create a

this works. Step by step, we create a 6x6 table. Six rows, the empty string

6x6 table. Six rows, the empty string plus the five letters of stone. Six

columns, the empty string plus the five letters of tower. Then we fill the first row and the first column with zeros.

These represent empty strings. And the

common subsequence of an empty string with anything is always zero. These are

our base cases. Now we go through the table cell by cell. In the first meaningful cell, we compare S and T.

They don't match. So we apply the second formula and take the maximum of the left and upper cells. Both are zero. So the

result is zero. That makes sense. S and

T have nothing in common. So we move to the next cell. Now we compare T and T.

They match. So we apply the first formula. We take the diagonal cell and

formula. We take the diagonal cell and add one. And we get one. Again, that

add one. And we get one. Again, that

makes sense. We found one matching letter. Then we keep moving forward. For

letter. Then we keep moving forward. For

a while, the characters don't match. So

the second formula keeps copying the best value we found so far. Then we

reach the cell where we compare two O letters. They match. So the first

letters. They match. So the first formula applies again. We take one from the diagonal and add one and we get two.

After that we again see a series of non-matching characters. But thanks to

non-matching characters. But thanks to the second formula, all remaining cells keep the best value so far. And then we finally reach a cell where we compare two E letters. They match. So once again

we apply the first formula and get three. Row by row. The entire table gets

three. Row by row. The entire table gets filled this way. In the end, the bottom right cell contains the maximum possible value because every step was trying to grow it when possible. That's the

answer. The length of the longest common subsequence toe. Now that the logic is

subsequence toe. Now that the logic is clear, let's talk about the code at a high level. First, we store the lengths

high level. First, we store the lengths of the strings in variables m and n just for convenience. Next, we create a

for convenience. Next, we create a two-dimensional array dp, our table, and fill it with zeros. This directly

represents our base cases. Then, we use two nested loops. The outer loop goes over the first string and the inner loop goes over the second. We start from index one because index zero corresponds

to the base cases. Inside the loops, we check the characters. If they match, we use the diagonal plus one formula. If

they don't, we take the maximum of the upper and left cells. When the loops finish, the entire table is filled and the answer sits in the bottom right corner. Clean and elegant. Let's quickly

corner. Clean and elegant. Let's quickly

estimate the complexity. For the time, we have two nested loops, each iterating over one of the strings. So the time complexity is O of M * N. Now the space,

we store a table of size M by N. So the

space complexity is also O of M * N. For

strings of length 1,000, that's about a million operations in a million cells, which is dramatically better than the naive 2 ^ of 1,000 approach. But now

let's look at the formulas again. We see

here that in order to compute the current row, we only ever need the previous row, nothing else. So we don't actually need to store the whole table again. We can keep just two rows, the

again. We can keep just two rows, the previous one and the current one, just as we've done in the grid problem already. Let's change the code then.

already. Let's change the code then.

First, we create two arrays, prev and current, and fill them with zeros. These

represent two rows of the table. And

inside the loop, we compute the current row using the same formulas as before.

We either look at the previous row or at the left cell in the current row. Then

after finishing a row, we just swap the arrays. The current row becomes the

arrays. The current row becomes the previous one and we move on and at the very end the answer is stored in prev n because of that final swap. Now the

space complexity is O of N instead of O of M * N. And if one string is shorter than the other, we can even get O of min of M and N. Even better. So now let's

summarize the key signs of the two sequences pattern. First, the problem

sequences pattern. First, the problem gives you two sequences, two strings, two arrays, two lists, something that needs to be compared. Second, you're

asked to find something in common or to count operations needed to transform one sequence into the other. A common

subsequence, edit distance, or something similar. Third, you build a

similar. Third, you build a two-dimensional table. One sequence goes

two-dimensional table. One sequence goes along the rows, the other along the columns, and the base cases sit on the edges. Fourth, the transition depends on

edges. Fourth, the transition depends on comparing the current elements. If

they're equal, you use one logic. If

they're different, you use another. So,

if you see a problem like this, draw the table where the two sequences intersect.

Fill the edges. then derive the transition formula based on how the elements compare. That's the two

elements compare. That's the two sequences pattern. Two-dimensional

sequences pattern. Two-dimensional dynamic programming for comparing two sequences. It's very similar to the grid

sequences. It's very similar to the grid pattern except that instead of a grid being given, you form the grid from two sequences. And once you understand this,

sequences. And once you understand this, you can solve a whole class of problems. Longest common subsequence, edit distance, shortest common super sequence, and more. The logic stays the

same. Only the formulas change slightly.

same. Only the formulas change slightly.

That's the real power of patterns. To

practice, let's solve the edit distance problem on Algo Monster. We're given two strings here and we need to find the minimum number of operations to convert one into the other. The available

operations are insert, delete, or replace a character. To understand what it means, let's look at the example here. If we have two strings, horse and

here. If we have two strings, horse and rose, then how can we turn horse into rose? Well, we'd need to replace H with

rose? Well, we'd need to replace H with R. That's one operation. Then we'd

R. That's one operation. Then we'd

remove the second R and get the word rows. Now that's the second operation.

rows. Now that's the second operation.

And then we'd remove E in the end to finally get rows. So three operations in total. But how do we solve this problem

total. But how do we solve this problem for any pair of strings? If we check all possible combinations of transformations, then their number grows exponentially, which is highly inefficient. So we could create a grid

inefficient. So we could create a grid based on these two strings where in each cell DPI J we'd store the number of operations to convert the first I characters from the first string to the

first J characters of the second string.

Just as before we'd also add row and column for an empty string as those are possible results too. But they also would give us the base cases. To convert

an empty string to any other string we'd need to just insert characters there. So

we can fill the first row and column in the grid with increasing numbers starting from zero. Now how do we calculate the rest of the cells? Well,

when considering two characters in two given strings, what are the possible scenarios? The first one, those

scenarios? The first one, those characters match. And that means we

characters match. And that means we don't need to apply any transformations to the first string. So we just take the number of operations we had for the previous substrings, which is DPI -1 J

minus one, the diagonal cell. But if the characters don't match, we need to apply some transformation. So there will

some transformation. So there will definitely be one new operation. But

then we need to choose the best option from all possible transformations we could apply to the previous substrings.

So we take the minimum of the diagonal, the top, and the left elements in the grid, which represent the values we'd get if we replaced, removed, or inserted a character in the previous substrings.

We're definitely adding one operation here. But as we don't know what previous

here. But as we don't know what previous transformation leads to the best result, we're considering them all and choosing the minimum one. Then in the bottom right corner of our grid, we'd have the final answer as it lies on the

intersection of the last characters of the full strings. For such a solution, we'd create a grid, which gives us O of M * M space complexity. And then we'd need to go over all the cells in this

grid to calculate this value. This gives

us O of M * M * complexity 2. Now let's

write the code for this approach. First,

I'll create two variables to store the lengths of two given strings. Then we

need to create our DP grid for storing the edit distances between all the substrings. But we'd add one to the

substrings. But we'd add one to the number of rows and columns as we also need to store values for empty strings.

The first column and the first row of this grid need to be filled with increasing numbers starting from zero.

So we just write two loops for that. And

now we can calculate the rest of the cells. To go over all of them, we need

cells. To go over all of them, we need two inner loops. And inside we use the two formulas we defined before. If we

have two matching characters in both strings, then we don't need to apply any new transformations. So we can just

new transformations. So we can just reuse the number of them for the previous substrings. That one is stored

previous substrings. That one is stored in the diagonal element. Otherwise, if

the characters don't match, we apply the second formula. We add one

second formula. We add one transformation and then choose the minimum of all the possible operations for the previous substrings. In the end, we return the value of the bottom right

cell of the grid. This is our answer for the two full strings. Running the tests and we see that our solution is correct.

Amazing. But this problem can also be solved recursively. You can check the

solved recursively. You can check the solution breakdown on the Algo Monster platform. Just click the link in the

platform. Just click the link in the description. Okay, we've learned how to

description. Okay, we've learned how to compare two strings. But what if you have just one string and you need to find something special inside it like a palendrome? That's where the next

palendrome? That's where the next dynamic programming pattern comes in.

Interval DP. And you'll see that it's actually very closely connected to what we already know. Here's a very popular problem. Longest palendroic subsequence.

problem. Longest palendroic subsequence.

You're given a single string and you need to find the length of its longest subsequence that reads the same in both directions. That's what we call a

directions. That's what we call a palendrome. A word or phrase that reads

palendrome. A word or phrase that reads the same left to right and right to left. ABBA is a palendrome. Radar is a

left. ABBA is a palendrome. Radar is a palendrome. But hello is not. And

palendrome. But hello is not. And

remember, a subsequence means the characters stay in the same order, but they don't have to be next to each other. We've already worked with this

other. We've already worked with this idea before. For example, in the string

idea before. For example, in the string modem, there is a subsequence mom and that subsequence is a palendrome. So our

task is to find the length of the longest palindromic subsequence in the given string. So how could we solve this

given string. So how could we solve this in a brute force way? In theory, we could generate all possible subsequences of the string. Then for each subsequence, we'd check whether it's a palendrome. Finally, we'd take the

palendrome. Finally, we'd take the longest one among all palendromes. But

here we fall into the same trap as before. How many subsequences does a

before. How many subsequences does a string of length n have? Exactly 2 to the power of n. That means this approach is incredibly slow. So we clearly need something smarter. Let's notice

something smarter. Let's notice something very important. A palendrome

reads the same from both ends. That

means the first character must match the last one. The second must match the

last one. The second must match the second to last and so on. Take the word radar. Why is it a palenrome? The first

radar. Why is it a palenrome? The first

letter r matches the last letter r.

Good. What's between them? Ada. And

that's also a palindrome. The first A matches the last A and in the middle there's just D which is a single character and any single character is a palendrome. Do you see the pattern? A

palendrome. Do you see the pattern? A

palendrome is made of two matching outer characters and a palendrome inside them.

And this observation changes everything.

Now we know that to find a palendrome in a larger part of the string, it's enough to know the answer for a smaller part.

Suppose we have the word total and we want to find the longest palendrome in the whole string. We look at the ends T and L. They're different. So these two

and L. They're different. So these two letters cannot both be part of the palendrome at the same time. So we have two options. Either the best palendrrome

two options. Either the best palendrrome lies in tota without the last letter or the best palendrome lies in odel without the first letter. If we already knew the answers for these two parts, we just take the maximum of them. That's it.

Take the part tota. Again, the outer letters don't match. So they also can't both be in the palendrome at the same time. We again have two options. Either

time. We again have two options. Either

look at tote or at oda. Take the part tote. The outer letters t and t match.

tote. The outer letters t and t match.

So both will be included in the palendrome and between them is O a single letter which by itself is a palendrome of length one. That's our

base case. It's always true for any single character. Then we add one and

single character. Then we add one and two for the two outer letters and get three. That's the length of the

three. That's the length of the palendromic subsequence. If we do the

palendromic subsequence. If we do the same check for the interval ODA, the best we can get there is one because there is no longer a palendrome. So now

going back to the interval tota, we see that inside it we have only these two possible sub intervals. So we choose the better of them and it turns out that inside tota the best palendroic

subsequence length is three. And now

when we look at the whole word it also has only two possible inner intervals.

Again we take the best of them. So we

get that three is the length of the longest palendroic subsequence in the entire string. Done. And the main thing

entire string. Done. And the main thing is that instead of 2 to the^ of n subsequences, we now work with intervals. And how many intervals can a

intervals. And how many intervals can a string of length n have? An interval is just a pair of numbers where i is the start and j is the end. The start can be from 0 to n minus one. The end from the

start to n minus one. In total, there are about n^2 over two such pairs. For a

string of length th00and, that's around 500,000 intervals. While the number of

500,000 intervals. While the number of subsequences would be 2 to the^ of 1,000, a number with 300 zeros. The

difference is enormous. And the key point if we compute the answer for every interval then the answer for the whole string is simply the interval from the beginning to the end. It covers the entire string. So we'll create a table

entire string. So we'll create a table where for each interval from I to J we store the answer the length of the longest palendrome in that interval.

We'll fill it step by step starting from small intervals and using them to compute larger ones. Let's see exactly how. In each cell of the table we store

how. In each cell of the table we store the length of the longest palendrome in the interval from I to J. Let's start

with something simple. What's the

longest palendrome in an interval of length one? Any single character is a

length one? Any single character is a palendrome. These are our base cases. We

palendrome. These are our base cases. We

can already fill the diagonal of the table with ones. Now for bigger intervals. How do we compute the length

intervals. How do we compute the length for an interval of length two or more?

We look at the outer characters of the interval in our string. First case, they match. For example, the interval taught.

match. For example, the interval taught.

If the outer letters match, they will definitely be part of our palendrome.

That's already plus two to the length.

What about the substring between them?

To define this inner interval, we move the left boundary one step to the right, I + 1, and the right boundary one step to the left, J minus one. That gives us the cell that stores the length of the inner interval. In this case, it's the

inner interval. In this case, it's the letter O, which is our base case. We

take that value and add two. Since in

total, the two outer letters match.

That's our formula, the cell for the inner interval plus two for the matching outer letters. But there's the second

outer letters. But there's the second case. When the outer characters are

case. When the outer characters are different, for example, the interval tal, the outer letters are t and l different. They cannot both be part of

different. They cannot both be part of the palendrome at the same time. So we

need to try without one of them. So

either we remove the left character and look at the inner interval. Removing the

left character means shifting the left boundary to the right i + 1 while keeping the right boundary the same j.

That's all. Or we move the right boundary j minus one and keep the left as is i. That's ta. Which of these is better? The maximum one. And that gives

better? The maximum one. And that gives us the formula for the case when the outer characters don't match. And you

remember that in the grid problem we went row by row top to bottom. But here

that won't work. Look at the formula. To

compute DPI J, we need DP I + 1 J minus1. The value for a smaller interval

minus1. The value for a smaller interval inside the current one. This means we must first compute all small intervals, then slightly larger ones, then even larger ones. We're not going rowby row

larger ones. We're not going rowby row in the table. We're going by interval length. First, all intervals of length

length. First, all intervals of length one. That's the diagonal. all ones, then

one. That's the diagonal. all ones, then all intervals of length two, then length three, and so on till we filled the whole table. Now, let's talk through the

whole table. Now, let's talk through the solution logic step by step. First, we

store the length of the string in the variable n for convenience. Then, we

create a two-dimensional array dp and fill it with zeros. This is our table.

At the same time, we go along the diagonal and put ones there because each character by itself is a palendrome of length one. And now, the main loop.

length one. And now, the main loop.

First, we iterate over interval lengths from 2 to n. This is how we ensure the correct order. First, we compute all

correct order. First, we compute all small intervals, then larger and larger ones. Then the inner loop goes over all

ones. Then the inner loop goes over all possible interval starts for the current length. We are checking all possible

length. We are checking all possible intervals of a specific length and they will start at different characters. And

at each step, we also need to know the end of the interval J. We can compute it like this since the start of the interval is I and its length is len. Now

we check if the outer characters match.

We apply our first formula. Take the

diagonal cell and add two. Otherwise, if

the characters are different, we use the second formula. We take the maximum of

second formula. We take the maximum of the two neighboring intervals. And when

all loops finish, DP0 n minus one will contain the answer because the interval from 0 to n minus one is exactly the whole string. That means this cell

whole string. That means this cell stores the longest palendrome for the entire string. Now, let's estimate the

entire string. Now, let's estimate the complexity. For the time, we have one

complexity. For the time, we have one loop over interval lengths and one loop over interval starts. Both run up to n.

So the total time complexity is O of N squared. And for the space, we store a

squared. And for the space, we store a table of size N byN. So the space complexity is also O of N^2. For a

string of length 1,000, that's about a million operations and a million cells, which is vastly better than the naive approach. But look at the formulas

approach. But look at the formulas again. To compute the current row, we

again. To compute the current row, we need values from that same row since I stays the same and from the next row where I is increased by one. So at each step we are again using only two rows in

the calculations. The previous ones are

the calculations. The previous ones are no longer needed. That means we can store only two rows instead of the entire table. So we can optimize the

entire table. So we can optimize the code. Now we create two arrays. Cur to

code. Now we create two arrays. Cur to

store the current row of the table and prev for the previous row. We initialize

them with zeros. Now we go over the rows from bottom to top from n minus one to zero. Why from the bottom? Because the i

zero. Why from the bottom? Because the i cell depends on i + 1. So we must first compute the lower rows. For each

position I, we set current cell to one.

This is exactly the diagonal element in the current row as if we had the full table. Then we iterate over all possible

table. Then we iterate over all possible interval ends for the start I. That is

the loop over J starts from i + 1 and goes to the end of the string. These two

loops together iterate over all possible intervals we have. And inside we apply the same formulas for each interval.

only now when we need to access the row below we use the prev array where that row is stored and when it's time to move up to the next row we swap our arrays so that the current row becomes the

previous one then we continue computing for the next intervals the final answer will be in prev n minus one because after the last iteration we swapped them

and now the space complexity is o of n instead of o of n^ squ since we store only two rows not the entire n byn table we've effectively cut it down along one

dimension. Let's highlight the signs of

dimension. Let's highlight the signs of the interval DP pattern so you can solve any task that uses it. First, in such problems, we work with a single sequence, not two. A string, an array,

just one structure. Second, usually we need to find an optimal result for an interval inside this sequence from position i to position j. Third, the

result for a large interval depends on the results for smaller intervals inside it. That is either the left or the right

it. That is either the left or the right boundary moves or both. Fourth, we fill the table by interval length, not rowby row. First short intervals, then longer

row. First short intervals, then longer ones. Fifth, base cases are intervals of

ones. Fifth, base cases are intervals of length one or sometimes zero. So if you see a problem where you need to optimize something inside one sequence by analyzing its parts, that's interval DP.

Examples of other problems using this pattern palendrome substrings burst balloons, coin game. The logic is the same everywhere. You build a table over

same everywhere. You build a table over intervals and fill it from smaller to larger ones. To practice, let's solve

larger ones. To practice, let's solve the palendromic substrings problem on Algo Monster. We're given a string here

Algo Monster. We're given a string here and we just need to count how many of its substrings are palendromes. So there

are n squared possible substrings in a string. And if we check each of them for

string. And if we check each of them for being a palendrome, we'd get O of N cubed total time complexity. But using

the interval DP pattern, we can solve this problem more efficiently. From the

previous problem, we know that in a palendrome the first and the last characters match and the intermediate part also forms a palendrome. So if we know that the intermediate interval is a palendrome and the last characters in

the substring match, then we can calculate in constant time that the substring from I to J is also a palendrome. Then we can just check all

palendrome. Then we can just check all possible substrings and run a recursive function for each of them that checks their first and last character and then executes itself for an inner interval between them. And it does that until it

between them. And it does that until it reaches an interval of just one character which is always a palendrome.

That's our base case. Whenever our

recursive function returns true, we increment the total counter of all the palendromes. And to not repeat the

palendromes. And to not repeat the calculations for the same intervals of larger substrings, we'll use memalization. As you see, interval DP

memalization. As you see, interval DP problems can also be solved recursively and sometimes it's easier than creating a grid. This solution gives us O of N

a grid. This solution gives us O of N squared time complexity as we need to check all the substrings. And thanks to memorization, we don't need to repeat any calculations and do them only once.

And for the space, we use memorization and store the result for each possible interval, which gives us O of N^ 2 space complexity. Let's now implement this

complexity. Let's now implement this approach. First of all, we need the LRU

approach. First of all, we need the LRU cache for our future memoization. Then

I'll create a variable storing the length of the given string just for convenience. Our initial Pendrrome

convenience. Our initial Pendrrome counter is zero. And then we just create two inner loops for checking all the substrings in the given one. Inside

we'll run our recursive function which we'll implement in a moment. If that one returns true, we just increment the total counter of palendromes. In the

end, we'll return that counter. But now

how does our recursive function look? It

accepts the start and end indexes of an interval being checked for a palendrome.

If the indices match or the start one is greater than the end one, then it's a base case, just an interval of one character. So we return true. Then if

character. So we return true. Then if

the first and the last characters in an interval don't match that's definitely not a palendrome. So we return false here. Otherwise we just run the

here. Otherwise we just run the palendromic check function for an inner interval which is from i + 1 to j minus1 and return its result. The last bit is

to add memization. It's easy in python.

We just add the lr cache annotation to our recursive function. Perfect. Let's

run the test to make sure that our solution is correct. And it works. You

can also check how this problem may be solved using the bottomup approach. Just

click the link in the description. Okay,

we've learned how to work with intervals. But there was one special

intervals. But there was one special thing there. To compute the answer for

thing there. To compute the answer for an interval, we only needed neighboring intervals. Sometimes though, to compute

intervals. Sometimes though, to compute the current element, you don't just need a couple of neighbors. You may need to check all previous elements. That's the

next dynamic programming pattern, non-constant transition. And now you'll

non-constant transition. And now you'll see how it's different from everything we've done so far. Here's a popular problem. Longest increasing subsequence.

problem. Longest increasing subsequence.

You're given an array of numbers and you need to find the length of the longest subsequence in which every next element is strictly greater than the previous one. A subsequence is when elements go

one. A subsequence is when elements go in the same order as in the original array, but not necessarily consecutively. We've already seen

consecutively. We've already seen subsequences in previous string problems. For example, in this array, the subsequence 1 2 4 is increasing.

Each next element is greater than the previous one. But 354 doesn't work

previous one. But 354 doesn't work because four is less than five. So we

need to find the longest such increasing subsequence. In this case, the answer is

subsequence. In this case, the answer is three because that's the maximum length for this array. How would you solve this head-on? Again, you could generate all

head-on? Again, you could generate all possible subsequences of the array. For

each one, check if it's increasing or not. Then find the longest among the

not. Then find the longest among the increasing ones. But here we fall into

increasing ones. But here we fall into the same trap as before. How many

subsequences does an array of length n have? For each element, you have two

have? For each element, you have two options. Either it's in the subsequence

options. Either it's in the subsequence or it isn't. So again, there are 2 to the^ of n possibilities. That means such an algorithm would run forever. But

let's think about it differently. We'll

build an increasing subsequence step by step, adding one element at a time.

Suppose you're looking at some element of the array and want to add it to a subsequence. When is that possible? Only

subsequence. When is that possible? Only

if it's greater than the last element of the sequence you already built. For

example, you have the sequence 1 2. The

last element is two. Can you add four?

Yes, four is greater than two. You get 1 2 4. Then can you add one? No, one is

2 4. Then can you add one? No, one is less than four. The sequence would stop being increasing. That's the key point.

being increasing. That's the key point.

To extend an increasing subsequence, the new element must be greater than the last one in it. Now, let's think in dynamic programming terms. We already know a lot. As usual, we'll create an

array DP where each cell will store the length of the longest increasing subsequence that ends at index i. Why

ends at i? Because when we want to extend some sequence, it's important to know what it ends with. Only then can we understand whether we can add the new element. And here we don't need a 2D

element. And here we don't need a 2D table because we're moving in one direction. A simple array is enough.

direction. A simple array is enough.

Let's start with something simple.

What's the longest increasing subsequence that ends at the first element of the array? Just that element itself. One element length one. Same for

itself. One element length one. Same for

any element which itself forms a subsequence of length one. So initially

all cells of our DP array contain one.

That's our base case. Now the fun part.

How do we compute the lengths for the other subsequences? Look closely. In the

other subsequences? Look closely. In the

staircase problem, we looked at two previous steps. In the grid problem, at

previous steps. In the grid problem, at two neighboring cells, in the palendrome problem, at neighboring intervals, there was always a fixed number of dependencies. What about here? Let's

dependencies. What about here? Let's

look at our array and go step by step.

We go left to right. We check whether element one can form an increasing subsequence with the previous elements.

There is exactly one previous element, three, at index zero. Since the

subsequence must be increasing, we check is the previous element smaller than the current one. No, three is greater than

current one. No, three is greater than one. So we can't extend the sequence

one. So we can't extend the sequence ending at three with one. It would stop being increasing. No suitable

being increasing. No suitable candidates. So DP at this position stays

candidates. So DP at this position stays one. Then we look at element five. It

one. Then we look at element five. It

could form a subsequence with any of the previous elements three or one. First we

check the increasing condition for three. Is three less than five? Yes. So

three. Is three less than five? Yes. So

we can extend the sequence ending at three. How do we compute the new length

three. How do we compute the new length at this element? We take the best length for that previous element from DP since that's the end of the subsequence and add one because we're adding one more

element to the subsequence five in this case. We get this formula but we can't

case. We get this formula but we can't stop yet because we have a second candidate subsequence that we can extend with five and we must check it too because it might turn out longer. We

check is one less than five? Yes, we can also extend the sequence ending at one.

Then we take its current best length from DP and add one again we get two.

So, we used both variants. We need to pick the maximum because we're looking for the longest subsequence. Since

they're equal, we store two for five.

The key point is we had to check both previous elements. You might think this

previous elements. You might think this feels like the staircase problem. Just

look at the two previous options, pick the maximum, and move on. But watch what happens next. Now, we need to compute

happens next. Now, we need to compute the length for element two. It already

has three previous candidates. Any of

the previous numbers can potentially form a subsequence with it. We must

check them all because in theory any one of them might give the best result not just the last two. So we compare two with each of the previous elements and if it's larger we compute our formula

then take the maximum among all valid options and store it in DP for this element. Then we go to the next element

element. Then we go to the next element and now we'll have to compare it with four previous elements not just two and pick the best option. See what's

happening at each step. The number of checks grows and we couldn't know in advance which previous element would give the best result. the three at the start, the one, the two in the middle, we had to check them all. And this is

fundamentally different from all the previous problems before. To compute the next result, we used a specific limited number of previous results. Here to

understand which subsequence we can extend with the next element, we need to check all previous elements. Any

previous element might be the end of some subsequence that we can extend with the current one. Which previous element do we choose? The one that gives the maximum length. So we get this formula.

maximum length. So we get this formula.

We iterate over all previous elements before the current one and compare each with the current element. If nums j is less than nums i, we can build an increasing subsequence. Then we take the

increasing subsequence. Then we take the current length for that subsequence dpj and add one for the new element. And

because we need the best option among all previous candidates, we take the maximum between this new value and what we already had in dpi. Now that we have the formula, writing the code is easy.

Let's go through it step by step. First,

we store the length of the original array in the variable n for convenience.

We create our DP array and immediately fill it with ones to set up the base case. Now, we iterate over all elements

case. Now, we iterate over all elements that will try to attach to previous subsequences. We start from the second

subsequences. We start from the second element because the first one has no previous elements to compare with. Then

comes our formula. We iterate over all elements before the current one. Compare

each with it. And if nums j is less than nums i, we add one to the length of the subsequence ending at j. Then we take the maximum among all values we've computed so far for this i. The final

result will be stored in one of the cells of the dp array. We just take the maximum from dp. That's the length of the longest increasing subsequence. Now

let's estimate the complexity time. The

outer loop runs in times. The inner loop runs on average about n over two times.

Overall it's o of m^ 2 space. we create

a DP array of length M. So it's O of N.

Even though we have quadratic time complexity, this is much better than the exponential complexity of the naive approach. It's a huge performance

approach. It's a huge performance improvement. We can't really optimize

improvement. We can't really optimize memory further here like in previous problems because at each step we need to check all previous DP values. So we

can't store less data. Quadratic

complexity is okay. But for very long arrays, we'd like something faster. And

there is a way. You can solve this in O of N log N using binary search. But

that's a completely different technique that goes beyond DP patterns. Let's

highlight the signs of the non-constant transition pattern. One, the state DPI

transition pattern. One, the state DPI depends not on a fixed number of previous states, but on a variable number, sometimes on all previous ones.

Two, you need to iterate over several or all previous candidates, and pick the best, usually a maximum or minimum.

Three, you get a nested loop, the outer one over the current position, the inner one over all candidates. Four, time

complexity is usually O of N squared because of the two nested loops, although sometimes you can speed it up with special data structures. Five,

memory optimization is usually impossible. You need all previous

impossible. You need all previous values. If you see a problem where to

values. If you see a problem where to compute the current state, you have to loop over and compare several previous ones. That's non-constant transition.

ones. That's non-constant transition.

Here are some examples of other problems. Longest batonic subsequence, maximum sum, increasing subsequence, box stacking. The idea is the same

stacking. The idea is the same everywhere. Iterate over all candidates

everywhere. Iterate over all candidates and choose the best one. Let's practice

with this pattern on Algo Monster.

Solving the problem called partition array for maximum sum. Here we are given an array of integers in an integer k.

And we need to partition this array into subarrays of lengths at most k. But

after we do that, each element in every subarray will be replaced by the max value of that subarray. and we need to return the largest possible sum of the whole modified array. Let's look at the example. If we have this array and k

example. If we have this array and k equals 3, then one of the ways to partition this one is to split it into these two subarrays. In this case, in each subarray, every element is replaced

with the max one. That is 15 in the first one and 9 in the second. Then the

original array becomes like that because its partitions were updated this way.

And by adding up all its elements, we get 72. This is the answer. And the

get 72. This is the answer. And the

thing is that there may be multiple ways to partition this array, but we need to find the way that gives the maximum sum.

Well, how do we solve that? Basically,

we know that our subarrays must be contiguous. So there will definitely be

contiguous. So there will definitely be some final subarray, right? It may be of length from 1 to k. Yes. But if we fix that last partition, the rest becomes an independent sub problem. For example,

for our original array and k equals 3, we could have these last subarrays potentially. And each of them gives us

potentially. And each of them gives us these remaining sub problems. So if we knew the best answer for each sub problem, then we just pick the right combination of them and that's it. And

that leads us to the DP solution. If we

create a DP array where at each element we store the max sum achievable by partitioning the first ey elements of the original array, then for DP6 for example, we can say that it's the

previous sum plus the maximum from all the last partition options we can have here. If we're looking for DP6, then we

here. If we're looking for DP6, then we have three options of the last partitions. If it's one element, then

partitions. If it's one element, then our formula is DP5 plus this one element because it's the max one in such a partition. Or we could have a partition

partition. Or we could have a partition of length two. Then to find DP6, we take DP4 and add the maximum of those two elements twice because there are two elements in the partition and they are

all being replaced by the max one. And

for the third option, there's the same logic. We take DP3 and add the max

logic. We take DP3 and add the max partition element three times to it. So

in the end to find DP6 we basically take the maximum one of these three options.

And this formula generalizes for every I we take all the partition lengths possible in a loop and then add together the previous sum before that partition and the max element of that partition

multiplied by its length. And if we go with such a solution, we'd create a DP array of length N, which gives us O of N space complexity. And as we loop through

space complexity. And as we loop through all the elements and all the possible lengths of partitions where K is the maximum one, we'd get O of N * K time complexity. So let's write the code for

complexity. So let's write the code for this one. It's quite short in fact.

this one. It's quite short in fact.

First, I create a convenient variable for storing the length of our array.

Then let's create our DP array. Now we

can loop through all its elements.

Inside we need a variable to store the maximum element per partition. Just

convenient. Then we start a loop over all possible partition lengths till k or the current element because we can be at the beginning of the array and won't be able to look back too far. That's why we

minimize the length here. Then inside a partition of a given length, we find the maximum element and store it in our variable. It's convenient here that we

variable. It's convenient here that we don't need to scan an entire partition looking for the max element all the time. As we increase the partition

time. As we increase the partition length by one on every iteration, we can just take the best option from the previous maximum and the new element in the partition. That's important so we

the partition. That's important so we don't get another k multiplier in our time complexity. And then we just apply

time complexity. And then we just apply our formula. We just take the maximum

our formula. We just take the maximum from the partition sum we've been able to find so far. And the previous sum for the current partition plus the max element of this partition multiplied by

its length as all the elements are replaced by it. And in the end, the last element in the DP array contains the answer for the problem. Let's run the test to make sure we've got it right.

And it works. The link to this problem is in the description, too. Okay, we've

learned how to work with subsequences in an array of numbers. But what if now we need to build a specific sum from the elements of this array? That's the next dynamic programming pattern. Knapsack

like problems. Here's a popular lead code problem. Partition equals subset

code problem. Partition equals subset sum. You're given an array of positive

sum. You're given an array of positive numbers and you need to determine whether it can be split into two parts so that the sum of elements in both parts is the same. Let's look at a concrete example. Here's the array. Can

concrete example. Here's the array. Can

we split it into two equal parts? Let's

compute the total sum. 1 + 5 + 11 + 5 = 22. That means each part must have a sum

22. That means each part must have a sum of 11. So, can we get 11 from these

of 11. So, can we get 11 from these numbers? Look, 1 + 5 + 5 = 11. Great.

numbers? Look, 1 + 5 + 5 = 11. Great.

What's left? The number 11. Also 11. So

from this array we can indeed form two groups that have the same sum and the answer to the problem is yes or true.

Now another example the total sum of all elements here is odd and if it's odd we can't split it into two equal parts.

Half of 11 is 5.5 and we only have integers. So the answer is no false and

integers. So the answer is no false and we can see that immediately without checking all combination okay how do we solve this problem in the general case the simplest way is to generate all

possible subsets of the array. For each

subset, we compute the sum and check if it equals half of the total sum. If yes,

that automatically means all remaining elements form the second half of the sum. So, we found a solution, but we hit

sum. So, we found a solution, but we hit the same problem as before. How many

subsets does an array of length n have?

For each element, there are two options.

Either it's in the subset or it's not.

So, again, two to the power of n options. Far too slow. So, let's think

options. Far too slow. So, let's think differently. We don't actually need all

differently. We don't actually need all subsets. We just need to know is it

subsets. We just need to know is it possible to get a specific sum. Imagine

you're packing a backpack. You have

items of different sizes and the backpack has a fixed capacity. No more,

no less. Question. Can you fill the backpack exactly without any remaining space using some of the items? That's

the classic knapsack problem. And our

problem is a special case of it. Here we

have numbers. These are our item sizes.

and we have two backpacks of the same capacity. We need to know whether we can

capacity. We need to know whether we can distribute the items between these two backpacks so that both are filled completely and all items are used. When

is this possible? Only if the total size of all items can be split into two equal halves, then each backpack must hold exactly half. But here's the fun part.

exactly half. But here's the fun part.

We don't actually need to try to fill both backpacks. If we can fill the first

both backpacks. If we can fill the first one exactly to half of the total sum, the second one is automatically filled by all remaining items. Their sum will be the other half. Now let's think in

dynamic programming terms. We need to check whether we can build the sum 11 from the array elements. Let's think

about how we build sums in general. Take

the first element one. What sums can we build now? Only zero if we don't take

build now? Only zero if we don't take anything and one if we take that one.

Add the next element five. Now we can build 0 1 as before. if we don't take five and also five and six by adding five to the old sums. Notice that we

don't duplicate 0 and 1 because we don't care about different ways to get them.

We only care whether they are possible at all. If we can get them in different

at all. If we can get them in different ways, great. They just stay. But new

ways, great. They just stay. But new

sums, we add. So with each new element, our set of reachable sums grows. We can

either take the new element, then we get new sums based on existing ones, or skip it, then previous sums remain. And each

next sum can be computed only from previously computed sums. These are all the variants we've managed to build so far in one way or another. And then we try to add the new element to each and see what we get. We hope that one of the

new sums will be the target. So we can apply dynamic programming here as well.

Because if we now add the next element, we'll again iterate over all past sums that were possible with previous elements and get more sums that include the new one. And one of them might be 11. That's exactly what we're looking

11. That's exactly what we're looking for. So, we need a way to store all

for. So, we need a way to store all previously reachable sums and most importantly avoid duplicates. If we keep storing duplicates, we'll end up with more and more repeated sums and again

blow up to exponential complexity. The

trick is to avoid duplicates so we don't do repeated work for each new element.

In previous problems, we used an array where indices matched element positions in the original array. And in the cells, we stored intermediate values for that element. But here that's not convenient

element. But here that's not convenient because for each element we get not one but several possible sums. We can't store them all inside a single cell. You

might say we could use a 2D array. But

then how do we eliminate duplicates nicely? Also not great. Here's the key

nicely? Also not great. Here's the key idea. What if we create an array where

idea. What if we create an array where the index is the sum we can build. Then

we make an array that has every index up to our target sum inclusive. Each cell

stores true if this sum is reachable and false if not. So index zero answers whether sum zero is possible. index

five, sum five, and so on. Then whenever

we discover a new sum, we just flip its flag to true in the array. And it's fast because we have direct access by index.

If we see the same sum again later, we look into its cell, see true, and leave it as is. No new entry is added. Now to

find the answer, we simply look at the cell with index 11. If after all computations, it's true, then we can build sum 11 from some elements of the array, and we don't care which exactly.

But how do we fill this array? That's

where our earlier observation comes in.

New sums are built from already reachable ones. Look closely. This is

reachable ones. Look closely. This is

the key moment. Let's take our first example. Target sum is 11. We create an

example. Target sum is 11. We create an array from 0 to 11. 12 elements in total. Initially, all values are false

total. Initially, all values are false except index zero because sum 0 is always reachable if we take nothing. All

other sums haven't been built yet, so they're false. Now we go through the

they're false. Now we go through the input array and add each element into our reachable sums. Take the first element one. We look at the sums we can

element one. We look at the sums we can currently build. We can always build sum

currently build. We can always build sum zero. Then we add one to it. We get a

zero. Then we add one to it. We get a new sum and we mark that index as true.

If we go further, all other cells are still false. So nothing else changes.

still false. So nothing else changes.

Take the next element five. We start

iterating over our sums. Sum zero is true. We add five to it and get sum

true. We add five to it and get sum five. Mark it as reachable. Next, sum

five. Mark it as reachable. Next, sum

one is also true. We add five to it and get sum six. Mark it as reachable, too.

So, we've got two new sums, but all previous ones also remain in our array.

We might need them later to build other sums. Take the next element again five.

Which sums were reachable? We could

build five and six, and they're still there. But now, we can also build 10 by

there. But now, we can also build 10 by adding 5 + 5. And we can build 11 by adding 5 + 6. At this point, the last cell becomes true, which means we've

reached our target. See the pattern? For

each element, we update our sums array like this. If we could previously build

like this. If we could previously build sum s, then now we can also build sum s plus num. The current value stays true

plus num. The current value stays true if it was already true. Or it becomes true if we can now reach that sum by adding the current element. But

unfortunately, this formula doesn't work as is. There's a very important detail.

as is. There's a very important detail.

Let's go back to the moment when we're processing the second element in our array. Five. If we use this formula, we

array. Five. If we use this formula, we start moving left to right through the sums array. We take zero, add five, mark

sums array. We take zero, add five, mark that sum. Then we take one, add five,

that sum. Then we take one, add five, mark that sum. So far so good. But our

loop must continue because for each element, we have to check all possible sums. There might have been larger sums before that could give us larger values forward. So we keep iterating. We go

forward. So we keep iterating. We go

over element by element. Most cells are false, so nothing changes. Then we reach index 5. It already stores true. We use

index 5. It already stores true. We use

it, add five, and get 10. But here's the problem. This cell represents a sum we

problem. This cell represents a sum we just computed using the very element we are currently processing. So we already added this element once and now we're adding it again. That's not allowed by

the problem. Each array element can only

the problem. Each array element can only be used once. So if we write the update formula while moving left to right, we run into this issue. How do we fix it?

We simply go from right to left instead.

Since adding a number always produces larger sums, all newly computed ones appear to the right while our movement is to the left. That means we will never touch these new values again in the same

iteration. To do that, we slightly

iteration. To do that, we slightly change the formula and run the loop from larger sums to smaller ones. Now let's

write the code to make sure everything is clear.

First, we compute the total sum of all elements in the array. Then, we check if the sum is odd. We immediately return false. It can't be split into two equal

false. It can't be split into two equal parts. So, we can't have two equal

parts. So, we can't have two equal backpacks. Next, we divide the total sum

backpacks. Next, we divide the total sum by two. This is our target sum. You can

by two. This is our target sum. You can

think of it as the capacity of one of the two backpacks we want to fill. Then,

we create our sums array and initially fill it with false. We set index zero to true because sum zero is always reachable. Then we go through each

reachable. Then we go through each number in the original array. That's the

outer loop. For each number, we need to walk through the sums array and update it from right to left. This is the trick that prevents us from using the same element twice. So, we start the inner

element twice. So, we start the inner loop at the target sum and go down to the current element. Why? Because in the formula, we subtract the current number

from the sum. The last index minus num should reach zero. This way we cover all valid sums up to the target. In the end, we return the value of the last cell in

the sums array. If it's true, the array can be split into two equal parts.

That's exactly the answer we need. Now,

let's estimate the complexity time. The

outer loop runs n times once per array element. The inner loop runs up to

element. The inner loop runs up to target times and target is at most half of the total sum of all elements. In the

worst case, that's O of N* sum space. We

create a sums array of size target + one. So O of sum. That's much better

one. So O of sum. That's much better than the naive exponential solution. Now

let's highlight the signs of knapsack like problems. First, you need to build a specific sum or reach some target value from the elements of an array.

Second, each element can be used a limited number of times, usually exactly once. Third, the order of elements

once. Third, the order of elements doesn't matter. Only the combination

doesn't matter. Only the combination does. Fourth, you create a DP array

does. Fourth, you create a DP array where the index is a possible sum and the value is whether it's reachable or what maximum or minimum you can get.

Fifth, you iterate over the array elements. For each one, you update DP

elements. For each one, you update DP from right to left if the element can be used once or from left to right if it can be used unlimited times. If you see a problem where you need to build a sum

or check whether some value is reachable from a set of numbers, that's a knapsack like problem. Here are some examples of

like problem. Here are some examples of other problems following this pattern.

Coin change, target sum, last stone weight two, ones, and zeros. In all of them, the idea is the same. You build an array of reachable values and updated element by element. For the practice,

let's solve the coin change problem on Algo Monster. We're given a list of

Algo Monster. We're given a list of integers called coins, and its values represent different coin denominations.

Also, we're given a total amount of money, and we need to find the fewest number of coins to make up that amount.

For example, we have coins of 1, two, and five. And we need to make up 11 with

and five. And we need to make up 11 with them. And the answer will be three

them. And the answer will be three because we can take two coins of value five and also one coin of one. That's

three in total. And to solve this problem, we can again create an array where each element number represents the sum we can collect. But the value of an element contains the minimum amount of

coins needed for this sum. So if we need to get 11 with these coins, then we create an array where the 11th index is the last one. And the base case would be zero because we need zero coins to get

the sum of zero. Then we go over this array and for each element we consider all the coin denominations we have. If

we want to get the amount of one which is our index here then what coins could we use? Only the coin of one. So we look

we use? Only the coin of one. So we look back at the previous sum without this coin which is zero and just add one coin to it. But here's where it gets

to it. But here's where it gets interesting. When we try to collect the

interesting. When we try to collect the amount of two which is this index we can get it in two ways. We can use a coin of denomination one. For that, we just

denomination one. For that, we just looked at the previous sum without this coin, which is DP1. But also, we could use a coin of denomination 2. So, we'd

look back at the previous sum without this coin, which is DP0. And then we'd take the minimum value of those two because we're minimizing the number of coins we need, and add one to it because we're adding one more coin to the

previous sum. And then we move on. For

previous sum. And then we move on. For

three, we again can use only coins of one or two. We cannot use five because it's too much to get three. So we again take the minimum of two previous values without these two possible coins and add

one to that. And only when we get to the amount of five can we consider all of the available denominations now. So

we're taking the minimum of the three previous values now. And then we move on with the same formula subtracting the available coin denominations from the current amount we're targeting and choosing the minimum from the previous

sums. This way when we get to the last element which is our target amount according to the problem we have the minimum amount of coins for that one too because we've been minimizing it all the way here and this is our answer. Solving

it this way would require creating an array of amount elements which gives us O of amount space complexity and we go through all the elements of that array where for each element we also check all

the coin denominations that gives us O of N * amount time complexity. Now

writing code for this one is easy as we've got the formula. First, let's

check a base case. If we need to collect the amount of zero, there are zero coins needed. Now, we can create our DP array

needed. Now, we can create our DP array and fill it with infinities because we'll be minimizing values in those cells. As we said, to get the amount of

cells. As we said, to get the amount of zero, we need zero coins. So, that's our base case in the array too. And now, we can run a loop over all the elements of this array. And inside, we'll also be

this array. And inside, we'll also be looping through all the coins we have.

First, we check that the coin is not too big. And we can actually look back at

big. And we can actually look back at the previous sums with that one. And

then we just use our formula. Take the

minimum of the previous sum without this coin plus this coin and we compare it with the number of coins currently stored in this cell because we might have got a better value with a different denomination already. In the end, we

denomination already. In the end, we just return the value in the last element of our array or minus one if we haven't been able to collect this amount with the given coins. Let's run the tests. Works perfectly. So you can now

tests. Works perfectly. So you can now go to the algo monster and solve this problem yourself. I hope you like the

problem yourself. I hope you like the video. If you want to practice more with

video. If you want to practice more with DP or any other coding techniques, please check out Aldommon Monster portal using the link in the description. There

are plenty of detailed explainers and other problems you can practice on.

Thank you for watching and I'll see you in the next