In this section, we are going to begin talking about a concept known as dynamic programming.
Dynamic programming is mainly an optimization over plane recursion.
So wherever we see a recursive solution, meaning that we have repeated calls for some input, we can
typically optimize that recursive solution by using dynamic programming.
Now, we're not going to spend too much time on dynamic programming, but it is a concept that I wanted
you to be familiar with.
So to start off, let's do a simple problem that we already know, which is the Fibonacci sequence.
So we did this in the recursive section, but there is a dynamic programming solution to this as well.
So we will create our function and we'll pass in an I 32 and return an I 32.
So we will create a couple of variables called A, B and C, So we'll say let me A, but B equals one.
It helps if I assign zero to A, and then we will say, Let you see, and then it's going to be of type
by 32.
So here we don't have to do any of our checks that we did in the recursive solution.
We can do a simple for loop and we don't care about where in the four loop we're at.
So we'll just designate it with the underscore and then we'll say from two and then include all the
way up to the value parameter that we're passing.
In that way, we also include that value and then we will simply say C equals A plus, B A is equal
to B, and then C B is equal to C, and now we want to return B, So probably looks a lot different
than our recursive solution, but we can test this out to make sure that it works properly so we'll
implement it.
A quick test case on it.
Mod tests use super, bring everything into scope and we will say we have a test case where we want
to test our Fibonacci out.
So in here we will say assert equals and we will say Fibonacci of nine and the result should be 34.
So if we run our test, try adding that would help for in.
Now if we run our test, we see that our test passed successfully.
So again, this was a very simple solution and I wanted you to get familiar with what dynamic programming
is.
And again, dynamic programming is used as an optimization over plane recursion.
So wherever we see a recursive solution, we can typically optimize it using dynamic programming.
And what we did here is we took our recursive Fibonacci solution and turned it into a dynamic programming
solution, and we see that it works just fine.
So now that we have a general understanding of what dynamic programming is, we will look at a couple
of additional problems to really solidify our learning on dynamic programming.
And we will start with looking at what the longest common sub sequences in the next lecture.