OK, guys, like I have seen you finally start studying computer science and competitive programming
only when you start the dynamic programming approach.
Now, a lot of students and I personally have had a lot of trouble with starting this chapter because
everything seems so counterintuitive and all the problems seems impossible to solve.
There is a lot of ideas like how can I get the array?
What information do I need?
Was the recurrence relation?
But I'm here to help.
And that's why from all the problems that they solved and all the moms, I really struggle with this
chapter.
I have developed a bullet proof formula for solving every problem of then.
And of course, there's a lot of mental exercise and creativity involved in solving this problem.
But at least you have a roadmap in how your solutions should look and what would be the steps in order
to achieve the solution.
So without further ado, let's first find out what is a dynamic program then any programming is a technique
that refers to simplifying a complicated problem into simpler problems in a recursive manner and then
solving the bigger problem, combining those problems together.
So this technique is suitable if the optimal solution of the problem can be well obtained by combining
together the optimal solution of some sub problems.
So you might ask yourself, OK, but what is the difference between dynamic programming and recursion?
Because from what I've heard from you until now, each problem I can solve with that technique sounds
like a recursive function, which calls itself over and over again for some problems and then merge
them together just like a divide and conquer approach, merge sort binary search and so on.
And you are right.
But I want to take your classical example, like the one I just hear is to actually show you the weak
point that the recursive solution would have and how dynamic programming solves that.
So I got on my whiteboard one or two serious.
And let's take a look.
As we know, it's a series in which the zero and one are equal to one and then the recurrence relation
is F is equal to F.I. minus one plus if I minus.
We can solve this problem obviously using a recursive approach.
In favor of end and one parameter, this function is going to return me, of course, F of N and if
N is less than two, we know the answer.
Return one.
This is the stopping point of the recursive function.
Otherwise return above and minus one.
Plus and minus two.
OK, seems really simple doesn't it.
If I just want to compute the after I just apply feebs of parameter N.
OK, and let's take a look.
OK and therms.
So I make any steps I compute end of this in terms of the series.
So should we be Gauvin.
Right.
Well that's false and let's see why.
Let's say I want to compute feebs of the time people nature and that is feed.
Then what do I do.
It's not less than two.
So I just apply five of nine plus people back to work, nine to five of it.
That's good.
Going here in this score, I want to compute of mine, which is going to be above eight plus five of
seven.
Again, above eight here is going to be FEBA of seven plus five of six and again five seven here fixes
here, five, six, five, five and so on.
So if you take a look at this recursion tree, we have ten some problems.
This is right.
All the terms from one to 10 or 11 auditorium's from zero to 10 doesn't matter.
But each such problem isn't solved only once because this friend of mine, OK, only one time great.
Above ten, only one time.
Great.
But let's take a look at five of eight.
I see it here and I see it here to at least two times.
People have seven one time.
Two times.
Three times, and that's it.
So now if you have seven is three times one five, six, one time, two, three times four times four
times fizbo.
Five one time, two times three times.
And I'm going to see it again from this group of sixes and so on.
So each problem is definitely solved.
A lot of times, and there's this parameter actually decreases that some problem is going to be solved
more and more times.
So the problem with this approach, the weak point, like I've said, is that it's a backtracking approach
because each problem is solved a lot of times.
Now, I can really tell the difference between dynamic programming and caution and that this dynamic
programming says, stop, I'm going to compute each problem exactly once and stole the result in memory
so I don't have to compute it again.
If you look at the recursion tree, the dynamic programming would say something like this.
For that, I need to apply for food night.
I need food aid.
And people said, let's take a look at 57.
Once they finish computing this value of five seven, I started the answer somewhere in the memory and
they won't.
Computed again in this quote.
So there's the whole different dynamic programming uses memory in order not to compute too many times
the same problem.
Now I'm going to clean the whiteboard and I'm going to see how to solve this problem using dynamic programming
approach and even better, how to solve it, using my bullet proof formula for these kind of problems.