Coding

# Dynamic Programming Example – Fibonacci

• 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: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