1
00:00:06,130 --> 00:00:12,040
In this section, we are going to begin talking about a concept known as dynamic programming.

2
00:00:12,610 --> 00:00:17,710
Dynamic programming is mainly an optimization over plane recursion.

3
00:00:17,710 --> 00:00:24,610
So wherever we see a recursive solution, meaning that we have repeated calls for some input, we can

4
00:00:24,610 --> 00:00:29,440
typically optimize that recursive solution by using dynamic programming.

5
00:00:30,910 --> 00:00:36,970
Now, we're not going to spend too much time on dynamic programming, but it is a concept that I wanted

6
00:00:36,970 --> 00:00:38,410
you to be familiar with.

7
00:00:38,680 --> 00:00:46,720
So to start off, let's do a simple problem that we already know, which is the Fibonacci sequence.

8
00:00:46,900 --> 00:00:54,310
So we did this in the recursive section, but there is a dynamic programming solution to this as well.

9
00:00:54,820 --> 00:01:01,450
So we will create our function and we'll pass in an I 32 and return an I 32.

10
00:01:01,720 --> 00:01:11,620
So we will create a couple of variables called A, B and C, So we'll say let me A, but B equals one.

11
00:01:11,620 --> 00:01:18,760
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

12
00:01:18,760 --> 00:01:19,810
by 32.

13
00:01:21,130 --> 00:01:28,210
So here we don't have to do any of our checks that we did in the recursive solution.

14
00:01:28,960 --> 00:01:35,320
We can do a simple for loop and we don't care about where in the four loop we're at.

15
00:01:35,320 --> 00:01:41,710
So we'll just designate it with the underscore and then we'll say from two and then include all the

16
00:01:41,710 --> 00:01:44,770
way up to the value parameter that we're passing.

17
00:01:44,770 --> 00:01:53,890
In that way, we also include that value and then we will simply say C equals A plus, B A is equal

18
00:01:53,890 --> 00:02:07,930
to B, and then C B is equal to C, and now we want to return B, So probably looks a lot different

19
00:02:07,930 --> 00:02:17,860
than our recursive solution, but we can test this out to make sure that it works properly so we'll

20
00:02:17,890 --> 00:02:18,610
implement it.

21
00:02:18,610 --> 00:02:20,230
A quick test case on it.

22
00:02:22,900 --> 00:02:34,930
Mod tests use super, bring everything into scope and we will say we have a test case where we want

23
00:02:34,930 --> 00:02:39,760
to test our Fibonacci out.

24
00:02:40,480 --> 00:02:54,640
So in here we will say assert equals and we will say Fibonacci of nine and the result should be 34.

25
00:02:55,810 --> 00:03:04,450
So if we run our test, try adding that would help for in.

26
00:03:05,920 --> 00:03:10,390
Now if we run our test, we see that our test passed successfully.

27
00:03:10,810 --> 00:03:18,400
So again, this was a very simple solution and I wanted you to get familiar with what dynamic programming

28
00:03:18,400 --> 00:03:18,970
is.

29
00:03:18,970 --> 00:03:25,360
And again, dynamic programming is used as an optimization over plane recursion.

30
00:03:25,360 --> 00:03:33,640
So wherever we see a recursive solution, we can typically optimize it using dynamic programming.

31
00:03:34,240 --> 00:03:42,070
And what we did here is we took our recursive Fibonacci solution and turned it into a dynamic programming

32
00:03:42,070 --> 00:03:45,550
solution, and we see that it works just fine.

33
00:03:46,000 --> 00:03:51,730
So now that we have a general understanding of what dynamic programming is, we will look at a couple

34
00:03:51,730 --> 00:03:57,070
of additional problems to really solidify our learning on dynamic programming.

35
00:03:57,070 --> 00:04:04,480
And we will start with looking at what the longest common sub sequences in the next lecture.