1 00:00:00,540 --> 00:00:02,610 Hey there and welcome back. 2 00:00:02,610 --> 00:00:09,960 In this video, let's discuss what approach should one take to be able to solve dynamic programming 3 00:00:09,960 --> 00:00:11,730 based coding interview problems? 4 00:00:12,330 --> 00:00:19,500 Now, when it comes to dynamic programming, many people directly start to draw a table like this. 5 00:00:19,500 --> 00:00:24,300 And then they put some initial values over here and go about it in this manner. 6 00:00:24,300 --> 00:00:29,850 Now, this is the wrong approach of approaching dynamic programming questions. 7 00:00:29,850 --> 00:00:30,510 All right. 8 00:00:30,510 --> 00:00:34,140 So they're trying to directly start with the tabulation approach. 9 00:00:34,140 --> 00:00:39,390 But then the problem is that you can memorize a few questions in this manner. 10 00:00:39,390 --> 00:00:43,980 But then when you're presented with a new problem you will not be able to solve it. 11 00:00:43,980 --> 00:00:50,490 So we will not be following this approach in this course, but rather the approach that we will be following 12 00:00:50,490 --> 00:00:56,940 is that first we will write the recursive solution to any dynamic programming question. 13 00:00:56,940 --> 00:01:02,550 And once we have written the recursive solution, we will be able to memorize it. 14 00:01:02,550 --> 00:01:06,780 Because remember memoization is just recursion plus storage. 15 00:01:06,780 --> 00:01:13,800 So after we are done with writing the recursive solution, we will just add a few lines of code to come 16 00:01:13,800 --> 00:01:16,080 up with the memoization approach. 17 00:01:16,110 --> 00:01:22,230 Again, remember this is just recursion plus storage, so we would just need to add a few lines to the 18 00:01:22,230 --> 00:01:26,010 recursive solution to come up with the memoization solution. 19 00:01:26,010 --> 00:01:31,530 Now the memoization solution is also called the top down solution. 20 00:01:31,530 --> 00:01:37,860 Once we are done with this, we will proceed to step number three, where we will use what we have learned 21 00:01:37,860 --> 00:01:43,290 over here to come up with the tabulation or bottom up approach. 22 00:01:43,290 --> 00:01:48,900 So again, the tabulation approach is where you write a table and it's an iterative approach. 23 00:01:48,900 --> 00:01:50,880 It's not a recursive approach. 24 00:01:50,880 --> 00:01:57,450 Now remember don't directly start with the tabulation approach, but rather first write the recursive 25 00:01:57,450 --> 00:01:57,960 approach. 26 00:01:57,960 --> 00:02:06,210 Then come up with the memoization and use these two to efficiently come up with the tabulation approach. 27 00:02:06,210 --> 00:02:12,210 Once we have written the tabulation approach, we will optimize this and come up with the space optimized 28 00:02:12,210 --> 00:02:13,710 tabulation approach. 29 00:02:13,830 --> 00:02:21,870 So these are the various steps that we will take in this course to understand various dynamic programming 30 00:02:21,870 --> 00:02:23,790 coding patterns thoroughly. 31 00:02:23,790 --> 00:02:31,560 Now, if you are not familiar with terms such as memoization and tabulation, don't worry about it. 32 00:02:31,560 --> 00:02:38,010 As we go on with the course, we will be discussing this multiple times and in detail for various coding 33 00:02:38,010 --> 00:02:41,310 interview questions, and then this will become second nature to you. 34 00:02:41,310 --> 00:02:45,420 Just remember, memoization is also called top down approach. 35 00:02:45,420 --> 00:02:50,280 And the tabulation approach is also called the bottom up approach. 36 00:02:51,150 --> 00:02:58,140 Remember, we had previously discussed that in dynamic programming, coding interview questions occur 37 00:02:58,140 --> 00:02:59,610 as part of patterns. 38 00:02:59,640 --> 00:03:06,900 Now, if you have taken these steps for, let's say, the first question in a series of questions which 39 00:03:06,900 --> 00:03:12,630 are of the same pattern, then for the second or third question, you will be able to directly come 40 00:03:12,630 --> 00:03:19,410 up with the tabulation or bottom up approach, because you have built a good intuition and good understanding 41 00:03:19,410 --> 00:03:21,630 of why this actually works. 42 00:03:21,630 --> 00:03:28,560 So again, remember if you encounter a deep question and if you are not able to solve it, take these 43 00:03:28,560 --> 00:03:29,100 steps. 44 00:03:29,100 --> 00:03:35,040 First, write the recursive solution, then memorize it and use the understanding that you gain from 45 00:03:35,040 --> 00:03:38,340 these two steps to come up with the tabulation approach. 46 00:03:38,340 --> 00:03:45,300 Let's now take this one step further and let's compare the top down and bottom up approaches. 47 00:03:45,300 --> 00:03:47,370 So over here I have a table. 48 00:03:47,370 --> 00:03:51,090 Now remember memoization is the top down approach. 49 00:03:51,730 --> 00:03:55,090 And tabulation is the bottom up approach. 50 00:03:55,180 --> 00:04:00,310 Now, there is an easy technique that I use to not confuse between these two. 51 00:04:00,340 --> 00:04:04,780 So notice over here we have a T for top down and for tabulation. 52 00:04:04,780 --> 00:04:05,800 Also we have a T. 53 00:04:05,830 --> 00:04:09,940 So I just remember that there is only one T at each site. 54 00:04:09,940 --> 00:04:15,640 So let's say I want to recollect whether tabulation is top down or bottom up. 55 00:04:15,640 --> 00:04:20,680 So what I think is that there is already a T, so I cannot have one more T. 56 00:04:20,680 --> 00:04:23,650 So it has to be a B which is bottom up. 57 00:04:23,650 --> 00:04:30,250 So again, this is just a quick way to correctly relate tabulation as the bottom up approach. 58 00:04:30,250 --> 00:04:36,460 So memoization is the top down approach and tabulation is the bottom up approach. 59 00:04:37,250 --> 00:04:43,850 Now let's compare between these two to solidify our understanding about these two approaches. 60 00:04:43,880 --> 00:04:52,940 Now memoization is called the top down approach because in memoization we start with the original or 61 00:04:52,940 --> 00:04:56,210 large problem which is called the top part. 62 00:04:56,210 --> 00:05:00,500 And then we proceed recursively till we hit a base case. 63 00:05:00,500 --> 00:05:04,460 And then we start returning and start computing the answer. 64 00:05:04,490 --> 00:05:12,920 But when it comes to tabulation, it's called bottom up because it starts with the smallest subproblem. 65 00:05:12,920 --> 00:05:14,900 And then it solves this. 66 00:05:14,900 --> 00:05:18,470 And then it uses this to solve larger problems. 67 00:05:19,070 --> 00:05:26,630 And again the smallest subproblem is what figuratively is called bottom of the problem hierarchy. 68 00:05:26,750 --> 00:05:31,580 Now we will see this more often when we solve actual coding interview questions. 69 00:05:31,580 --> 00:05:36,440 But over here let me just give you an intuition of what this actually means. 70 00:05:36,470 --> 00:05:42,380 We had seen previously the Fibonacci question where we had various branches like this right now. 71 00:05:42,380 --> 00:05:49,310 Remember in the recursive approach, the algorithm would go down a branch, and then once it hits a 72 00:05:49,310 --> 00:05:52,640 base case, it will start computing and returning. 73 00:05:52,640 --> 00:05:59,150 So that's why over here we can say that it starts with the original or large problem which is over here. 74 00:05:59,150 --> 00:06:00,650 And then it goes down. 75 00:06:00,650 --> 00:06:02,870 So this is called the top down approach. 76 00:06:02,870 --> 00:06:09,140 But for the Fibonacci question we had also discussed that we could theoretically just have a table like 77 00:06:09,140 --> 00:06:09,590 this. 78 00:06:09,590 --> 00:06:12,020 Let's say we are trying to find f of five. 79 00:06:12,020 --> 00:06:13,760 So we have a table over here. 80 00:06:15,210 --> 00:06:18,270 And we know that f of zero is zero and f of one is one. 81 00:06:18,270 --> 00:06:22,380 And then we just go ahead and find f of two which is adding zero and one. 82 00:06:22,380 --> 00:06:23,040 That's one. 83 00:06:23,040 --> 00:06:26,580 And then we find f of three which is adding these two which is two. 84 00:06:26,610 --> 00:06:31,260 So in this case notice that we are starting over here by finding f of two. 85 00:06:31,260 --> 00:06:34,650 And we are filling these to find the answer of f of five. 86 00:06:34,650 --> 00:06:36,420 So that's what we say over here. 87 00:06:36,420 --> 00:06:43,170 Tabulation starts with the smallest subproblem which is called figuratively the bottom of the problem 88 00:06:43,170 --> 00:06:43,920 hierarchy. 89 00:06:43,920 --> 00:06:45,870 And that's this place over here. 90 00:06:45,870 --> 00:06:50,670 So again we have seen an interesting distinction between memoization and tabulation. 91 00:06:50,670 --> 00:06:53,580 Now let's take a look at one more interesting point. 92 00:06:53,580 --> 00:06:57,420 Remember memoization is a recursive approach. 93 00:06:57,660 --> 00:06:59,880 It's just recursion plus storage. 94 00:06:59,880 --> 00:07:02,940 But tabulation is an iterative approach. 95 00:07:03,360 --> 00:07:06,570 So we are just iterating from two up to five. 96 00:07:06,570 --> 00:07:10,230 And we keep calculating these values and we store them over here. 97 00:07:10,230 --> 00:07:17,400 So in this video we have discussed the approach which is ideal to master dynamic programming coding 98 00:07:17,400 --> 00:07:18,390 interview questions. 99 00:07:18,390 --> 00:07:25,530 And we have also discussed the difference between memoization and tabulation when we discussed the approach, 100 00:07:25,530 --> 00:07:32,490 which is ideal for mastering dynamic programming questions, we mentioned that it's ideal to first start 101 00:07:32,490 --> 00:07:39,030 with the recursive solution and then memoize it before we proceed and write the tabulation approach. 102 00:07:39,030 --> 00:07:45,840 In the next video, let's develop some intuition regarding why writing the recursive solution and then 103 00:07:45,840 --> 00:07:50,670 memorizing helps us to effectively come up with the tabulation approach.