Then I'm not going to gain much.
The, the, the gain I would get from this if the same sub-problem, is,
needs to be solved over and over and over.
With dynamic programming, the way we do that.
By solving it only once, storing it in a matrix and every time we need to solve it
again, all we do is just, look up the value in the matrix, okay?
The other thing that we have to keep in mind,
that the fact that I have written this, this kind of formula and this algorithm.
Does not necessarily mean, or if I have dynamic programming,
does not necessarily mean I have an efficient algorithm, or
a polynom, which we mean polynomial time algorithm.
For this to be polynomial, the sub problems, that we divide and
solve, has to be polynomial as well, okay?
Because, if you, have to solve, if the matrix has exponential size.
There's nothing much you can do about it, because you are filing the entire matrix.
So usually the running time, of a dynamic programming algorithm,
is dominated by the size of matrix because, or the size of it,
the size of matrix because, we have that entries in the matrix.
At least we have to fill out these entries in the matrix.
Even if we do the simplest amount of computation,
which is constant number of operations per entry, the number of
entries in the matrix, is going to give us a lower bound, on the running time.
Now, what is the running time of this algorithm?
It's very simple to analyze, actually.
This loop here is on the order of n, right.
n minus five, it is order of n.
This here is also in the order of n because in the, in the,
in the worst case, n is five and this is going to go from one to n minus five.
This is o of one.
Here, this is going to be O(1).
Of course this is O(1), O(1), the addition is O(1) but
there is this [BLEEP] that is ranging.
If I am looking again in the worse case at position N,
T could be, any of these positions here.
So in the worse case, it is O(n).
So this we see, in the worse case we might be looking at O(n) values.
So, this can be O(n).
So O(n), this is nested within it, this is nested within this.
So this algorithm, is in the order of nq.
Okay?
And this is much better than trying a brute force approach,
that would have tried, for example, let's look at every possible way of pairing.
Indexes in the [INAUDIBLE] secondary structure and then check feasibility, and
then find the one with the maximum number, okay?
And, if you,
if you want to think about, is this faster than the recursive algorithm?
I en, I highly encourage you to implement this, as a,
in dynamic programming; using a matrix.
Just implement this using the recursive version,
where this opt is the name of the function instead of a matrix.
So you call, that you are calling the function here every time.
And run them and look at the running time of these two algorithms and
see which one is going to be faster.