1 00:00:01,230 --> 00:00:02,260 Welcome back, everyone. 2 00:00:02,820 --> 00:00:06,950 Hopefully, the challenge was not too hard if you managed to figure it out, that's great. 3 00:00:06,960 --> 00:00:08,690 If not, let's just do it together. 4 00:00:09,300 --> 00:00:13,380 The first thing that we need to do is modify our initial calling function. 5 00:00:13,710 --> 00:00:17,720 We're also going to modify what we pass into our recursive function as well. 6 00:00:17,730 --> 00:00:22,290 So we might as well remove everything here and just start from the very top. 7 00:00:22,680 --> 00:00:25,980 We're going to keep the const end because that's not going to change. 8 00:00:26,430 --> 00:00:31,140 But now we're going to initialize some type of object that will save the values. 9 00:00:31,140 --> 00:00:33,900 And I'm going to call it DPE for dynamic programming. 10 00:00:34,200 --> 00:00:37,740 And it's going to be equal to an empty array as we know. 11 00:00:37,740 --> 00:00:42,820 We want to match the data structure to whatever data structure we receive that we iterate through for 12 00:00:42,820 --> 00:00:43,460 our answer. 13 00:00:44,280 --> 00:00:48,830 Next, what we're going to do is we are going to return the same thing we had before. 14 00:00:49,050 --> 00:00:50,160 So math dustmen. 15 00:00:52,450 --> 00:00:55,120 Between calling our min cost. 16 00:00:56,770 --> 00:01:02,260 On IE minus one, which receives the Costa, but now also our DPE. 17 00:01:03,240 --> 00:01:05,370 As well as men cost. 18 00:01:06,440 --> 00:01:12,140 I'm minus two, which now receives the cost as well as deep as well. 19 00:01:14,230 --> 00:01:20,170 That's the main change to the original calling function, ask for our recursive function, we now have 20 00:01:20,170 --> 00:01:23,020 to add the fact that we receive a DP. 21 00:01:24,140 --> 00:01:31,550 Inside of our arguments and inside here, we need to think about what we're going to do to both retrieve 22 00:01:31,550 --> 00:01:36,680 the appropriate value if it already exists, but also store the appropriate value if it also exists. 23 00:01:36,980 --> 00:01:39,590 So first, I'm just going to remove this initial caller. 24 00:01:40,770 --> 00:01:42,920 Our base cases actually stay the same. 25 00:01:43,860 --> 00:01:49,140 Because these don't really have any type of scaling impact on our performance and they only suit to 26 00:01:49,140 --> 00:01:51,120 help us, we know that that's not going to change. 27 00:01:51,720 --> 00:01:56,340 What will change, though, is that what we have to do before we run the calculation? 28 00:01:57,030 --> 00:02:03,460 We need to check if the value exists in DP already and we're going to store it in DP at the index. 29 00:02:03,480 --> 00:02:12,450 So what we're going to say is that if the DP value at the current index is not equal to anything, so 30 00:02:12,450 --> 00:02:19,200 if it is not undefined, so we'll say as long as I is not equal to undefined. 31 00:02:20,790 --> 00:02:25,590 Because the value could be zero, so we can't just assume it'll be Truthy if this happens, then we 32 00:02:25,590 --> 00:02:29,030 just want to return what we have at DPE at I. 33 00:02:30,880 --> 00:02:32,960 Otherwise, we want to store the value. 34 00:02:33,430 --> 00:02:34,660 There is no value here. 35 00:02:34,680 --> 00:02:36,280 We have to calculate it manually. 36 00:02:36,290 --> 00:02:39,700 So let's say I is equal to what we had before. 37 00:02:40,100 --> 00:02:44,980 So it's going to be the cost that I plus the math dustmen. 38 00:02:46,970 --> 00:02:56,270 Between our men cost recursive call on AI minus one passing and the same cost array and passing in our 39 00:02:56,270 --> 00:02:57,260 current DPE. 40 00:02:58,330 --> 00:03:05,430 Similarly, we're going to do the same thing for I minus two, same cost, the same DPE. 41 00:03:07,040 --> 00:03:13,520 Once we started in the DPI, normally we just return this value, but instead we're going to return 42 00:03:13,520 --> 00:03:15,830 the value that we've saved in DPI. 43 00:03:15,830 --> 00:03:18,390 So we'll return DPI at EI. 44 00:03:19,970 --> 00:03:24,170 And now this is our modified function, that's all it is. 45 00:03:25,010 --> 00:03:30,510 What you want to think about now is what does this do to our performance? 46 00:03:30,560 --> 00:03:35,270 Remember before that we had a space and time of two to the power of end. 47 00:03:36,140 --> 00:03:43,880 Now, what we have instead is we've managed to lower down the number of iterations we have to do, because 48 00:03:43,880 --> 00:03:50,230 if the value exists, we don't build out that branch, which means that this entire section where i3 49 00:03:50,240 --> 00:03:53,450 gets calculated, this will actually not even run. 50 00:03:53,690 --> 00:03:56,840 We're just going to end up retrieving the value in DPE. 51 00:03:57,020 --> 00:04:01,000 So this entire branch has already been calculated before. 52 00:04:01,550 --> 00:04:03,440 We're not going to do anything here. 53 00:04:03,890 --> 00:04:08,600 Similarily I three here is also not even going to get calculated. 54 00:04:10,210 --> 00:04:14,660 Because we've already memorized the value here and here I for as well. 55 00:04:14,680 --> 00:04:16,450 We've already calculated everything here. 56 00:04:16,460 --> 00:04:19,420 We're just going to retrieve the value that DPE has stored. 57 00:04:19,930 --> 00:04:26,260 So what you see is that we save ourselves on so many calculations as essentially we just calculate everything 58 00:04:26,260 --> 00:04:29,480 from AI all the way down to zero one time. 59 00:04:29,920 --> 00:04:37,720 So what this means is that our time complexity goes down to O of N where N is the size of your array. 60 00:04:38,380 --> 00:04:45,490 As for space, space also goes down to O of N because our recursion tree is only going to grow to the 61 00:04:45,490 --> 00:04:52,510 size of N since as I mentioned, we're only doing N calculations and our DP is also going to be of size. 62 00:04:52,510 --> 00:04:59,040 And because of course we're storing a value at every single index that exists inside the cossa. 63 00:04:59,050 --> 00:05:00,570 So it's equal to the same length. 64 00:05:01,240 --> 00:05:06,950 So it's two and you drop the two, you end up with n space and time are both O of end. 65 00:05:07,660 --> 00:05:10,940 This is the full entirety of the top down approach. 66 00:05:11,110 --> 00:05:16,540 You figure out the recurrence relation, you get the formula, you use the formula to derive an initial 67 00:05:16,540 --> 00:05:19,600 recursive solution from this recursive solution. 68 00:05:19,750 --> 00:05:25,930 You draw a state based tree or you mentally map out a state based tree and figure out where you're wasting 69 00:05:25,930 --> 00:05:26,560 cycles. 70 00:05:27,040 --> 00:05:32,950 Then you utilize some type of memorization where you create some data structure that's equal to the 71 00:05:32,950 --> 00:05:36,310 object that you're iterating through or the data structure that you're learning through. 72 00:05:36,790 --> 00:05:42,070 And then you fill it into your existing solution by replacing it where you need to either pull the value 73 00:05:42,070 --> 00:05:43,660 out or calculate the value. 74 00:05:43,900 --> 00:05:48,270 And then now you have a much faster, vastly optimized algorithm. 75 00:05:48,580 --> 00:05:51,430 We went from two to the power of N down to O of N. 76 00:05:51,670 --> 00:05:53,560 That is an incredible savings. 77 00:05:53,890 --> 00:05:59,470 That's why dynamic programming is so powerful, but it's such an extensive step through process to get 78 00:05:59,470 --> 00:05:59,730 to. 79 00:06:00,220 --> 00:06:02,560 And this is just the top down process. 80 00:06:02,830 --> 00:06:11,260 We can actually optimize our solution in such a way that we can go and save ourselves on our space complexity. 81 00:06:11,440 --> 00:06:13,860 Time does not actually get any better at this point. 82 00:06:13,870 --> 00:06:17,830 This is the best time complexity, but we can improve space complexity. 83 00:06:18,310 --> 00:06:22,630 Remember, what I've mentioned is that up until this point, what we've done is known as the top down 84 00:06:22,630 --> 00:06:23,110 approach. 85 00:06:23,590 --> 00:06:30,190 From this top down approach, you've managed to identify what the top down tree build looks like here. 86 00:06:30,190 --> 00:06:36,550 The next approach is going bottom up where you build from your base values at the very bottom here, 87 00:06:36,550 --> 00:06:41,650 including your base cases, and you build up to a solution and you can do it in an iterative manner 88 00:06:41,650 --> 00:06:43,020 instead of a recursive manner. 89 00:06:43,360 --> 00:06:48,000 I do want to mention that this top down approach for your interview questions is enough. 90 00:06:48,010 --> 00:06:53,290 It's very, very unlikely that in your interview they're going to expect you to go through the full, 91 00:06:53,290 --> 00:06:59,230 deep process where you finish the top down approach and then transition to a bottom up approach. 92 00:06:59,530 --> 00:07:01,770 Finding the bottom up is very challenging. 93 00:07:02,110 --> 00:07:07,420 It's actually just as hard as finding the recurrence relation because you're looking for a new relationship 94 00:07:07,420 --> 00:07:09,370 to rewrite your algorithm. 95 00:07:10,350 --> 00:07:15,960 But what we're going to do at the very least, is explore what that path looks like, but I do want 96 00:07:15,960 --> 00:07:21,780 you to know that it's not always expected that you are going to have to do the bottom up approach as 97 00:07:21,780 --> 00:07:22,050 well. 98 00:07:22,620 --> 00:07:26,330 Reaching this point should be your main focus with dynamic programming. 99 00:07:26,490 --> 00:07:32,790 If you are constrained on time, if you have a lot of time, then of course practice the full entirety 100 00:07:32,790 --> 00:07:33,930 of dynamic programming. 101 00:07:34,290 --> 00:07:39,900 Doing it will only benefit you with getting a deeper understanding of why dynamic programming is a great 102 00:07:39,900 --> 00:07:41,040 algorithmic paradigm. 103 00:07:41,370 --> 00:07:42,820 But that's my warning for you. 104 00:07:43,170 --> 00:07:48,420 So for us, let's try and figure out how we can convert this into the bottom up approach and why that 105 00:07:48,420 --> 00:07:50,130 improves our space complexity.