- 00:00:00 what's up guys in a previous video I
- 00:00:02 showed that solving for the nth
- 00:00:04 Fibonacci number by a brute-force manner
- 00:00:07 is upper bounded by O to the to the N
- 00:00:11 time this is an exponential run time so
- 00:00:14 it's not very good in this video we're
- 00:00:17 going to use dynamic programming to show
- 00:00:19 how you can speed that up to O of n to
- 00:00:23 find the nth Fibonacci number in order
- 00:00:27 to solve this problem using dynamic
- 00:00:28 programming we'll have to follow a
- 00:00:30 couple simple steps the first is to
- 00:00:33 identify optimal substructure I'll
- 00:00:35 explain this in just a second next we
- 00:00:38 need to define our recursion we need to
- 00:00:41 add base cases and then finally the
- 00:00:44 runtime of our dynamic programming
- 00:00:45 solution will be the number of
- 00:00:48 subproblems that we find and then
- 00:00:50 multiply that by the time per
- 00:00:51 sub-problem
- 00:00:52 so what optimal substructure means is
- 00:00:55 that the optimal solution to your
- 00:00:57 problem is built up of the optimal
- 00:01:00 solutions to smaller subproblems so
- 00:01:03 here's what I mean the black numbers
- 00:01:06 represent the first seven Fibonacci
- 00:01:08 numbers and then the red represents the
- 00:01:11 index of those Fibonacci numbers so if
- 00:01:15 we wanted to calculate the seventh
- 00:01:16 Fibonacci number here which is 13 to
- 00:01:20 find that we just need to add together
- 00:01:22 the fifth and the sixth Fibonacci
- 00:01:24 numbers so 5 plus 8 equals 13 so the
- 00:01:29 Fibonacci sequence exhibits optimal
- 00:01:32 substructure because the solution to the
- 00:01:35 seventh Fibonacci number was built up of
- 00:01:37 these smaller five and six Fibonacci
- 00:01:40 numbers the next step to solve a dynamic
- 00:01:43 programming problem is to define the
- 00:01:45 recursion and the Fibonacci sequence
- 00:01:47 this is very easy the definition of the
- 00:01:49 Fibonacci sequence is that the nth
- 00:01:51 Fibonacci number is the sum of the N
- 00:01:55 minus first Fibonacci number plus the n
- 00:01:59 minus second Fibonacci number one
- 00:02:03 important thing to note with this
- 00:02:05 recursion is that in order to make it
- 00:02:07 effective we're going to have to utilize
- 00:02:08 a technique called memoization what
- 00:02:12 memorization means
- 00:02:13 is basically we need to save solutions
- 00:02:16 to our subproblems so as you can see in
- 00:02:19 this recursion n is composed of n minus
- 00:02:22 1 plus n minus 2 and so forth the
- 00:02:26 important thing to see here is that as
- 00:02:28 we progress through this recursion there
- 00:02:31 are values that are calculated multiple
- 00:02:33 times so n minus 2 n minus 3s and if we
- 00:02:38 were to expand this further you would
- 00:02:40 see that there are a ton of things that
- 00:02:42 we are calculating when we don't need to
- 00:02:44 so we need to utilize em memoization
- 00:02:46 that means that whatever we calculate
- 00:02:48 the solution to a sub-problem we're
- 00:02:50 going to save it so we would save and
- 00:02:52 minus two we'd save and minus three we'd
- 00:02:55 save and minus 1 etc so that when we
- 00:02:59 finally get to the point where we can
- 00:03:01 calculate this n value these values are
- 00:03:03 already saved and we can compute the
- 00:03:05 computation in a one-time encode this
- 00:03:12 looks as follows we begin by
- 00:03:14 initializing an empty dictionary to
- 00:03:16 store our memorized values then we plug
- 00:03:18 in an arbitrary N and for the purpose of
- 00:03:21 this example let's assume that it's a
- 00:03:22 lot larger than 2 now we begin our first
- 00:03:25 iteration on the first iteration this
- 00:03:28 line will not execute because our memo
- 00:03:30 table is currently empty
- 00:03:31 also our n value is a lot larger than 2
- 00:03:34 so this will NEX Qt there the first
- 00:03:36 execution will happen on line 7 and as
- 00:03:39 you can see that's when the recursive
- 00:03:41 calls happen these recursive calls will
- 00:03:46 go back to the top and continue down
- 00:03:49 until we eventually hit this base case
- 00:03:51 from there we'll start filling in our
- 00:03:54 memo table
- 00:04:04 this process of filling our memo table
- 00:04:07 continues until we have the N minus
- 00:04:11 first and the N minus second values in
- 00:04:13 our table then finally we can compute
- 00:04:17 this addition in oh one time this leads
- 00:04:23 us to our last step of computing the run
- 00:04:25 time as previously stated the run time
- 00:04:28 is equal to the number of subproblems
- 00:04:32 times the time per each sub-problem the
- 00:04:43 number of subproblems is going to be on
- 00:04:45 the order of the number of terms we had
- 00:04:47 to memorize so in this case when we are
- 00:04:49 calculating end we had to memorize n
- 00:04:51 minus 1 n minus 2 all the way down to
- 00:04:54 our base cases of 2 and 1 this in total
- 00:04:58 is on the order of n terms so the number
- 00:05:01 of subproblems we have is o of n next to
- 00:05:04 calculate the time per sub-problem
- 00:05:06 is simply just an eighth edition so to
- 00:05:08 calculate n we just needed to add n
- 00:05:10 minus 1 plus n minus 2 because we
- 00:05:14 memorize both of these terms we can do a
- 00:05:16 constant look at lookup of them so this
- 00:05:19 whole addition is going to be a 1 so if
- 00:05:24 we combine these two terms we get the
- 00:05:26 final runtime of dynamic programming
- 00:05:28 solution to the Fibonacci sequence is o
- 00:05:32 of n this is our time thank you guys for
- 00:05:38 watching if you liked this video please
- 00:05:40 give it a thumbs up and if you have any
- 00:05:42 advice on future videos I should make
- 00:05:44 please let me know in the comments
