So now we have,

we have reasoned about how to solve the [INAUDIBLE] structure problem.

And we got to our recursive formula, which we said,

we can easily just now turn it into a recursive, recursive algorithm.

How do recursive algorithms work?

Again, recursive, the recursive algorithm is going to start from opt of 1N,

and then it's going to start breaking the problem into smaller problem, and

solving, and solving, and solving.

If you think about it, if you try that algorithm and you look at it carefully,

you will see that there will be many times where you for

example opt of IJ will be solved over and over and over again for a same I and J.

Okay?

So the, one of the issue with recursive algorithms in these kind of problems.

Is that there are some problems that are going to appear multiple times when we

break the problem into sub-problems.

And these sub-problems are going to be solved again, over and over and over.

Now instead of doing that,

how about when we solve a sub-problem, we store the value.

So when we solve opt of I J, we store the value of opt I J.

And then next time we see, next time we encounter opt of I J,

instead of solving that again, which will take time, we can just look up the,

the value of that I J in a matrix, I by J.

Right?

And this is actually the, the, the technique that we,

I'm going to show now, or the implementation of that, of that algorithm.

That instead of doing recursive implementation is going to

store values in a table and every time we need,

we need a value instead of re-computing it we'll just look it up in a table.

And this the, this is the implementation here of the algorithm I just described.

Again, I'm going to, I'm going to start.

Instead of, of starting opt of 1 N,

I will starting from opt of, of I J from smaller values of I J.

From 1, 1, 1, 2, and so on, and go all the way and build towards opt of 1 N.

So, wha, first thing is I, I can op, initialize opt of IJ to zero for

every case where I is greater than or equal to J minus 4.

because remember, the no sharp turns say that i has to be smaller than J minus 4.

So, for every case where I is greater than or equal to minus 4.

This can't, this has to be zero.

I cannot have any pairs, in the, in the set.

So, now that, that this is the case, I can initialize k from 5 and onwards,

and I start with the sequence with the onward sequence from position 1 to,

all the way to N minus K.

When I look at position 1, in my a, in my RNA sequence.