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