1
00:00:00,110 --> 00:00:01,010
Welcome back.

2
00:00:01,010 --> 00:00:04,970
So this is the recursive solution that we had previously written.

3
00:00:04,970 --> 00:00:07,160
Now let's go ahead and memorize this.

4
00:00:07,160 --> 00:00:08,180
And you will see that.

5
00:00:08,180 --> 00:00:11,390
To do that we will just be adding a few lines of code okay.

6
00:00:11,390 --> 00:00:14,630
So let me add a memory over here.

7
00:00:15,680 --> 00:00:18,620
And this array will have the size n okay.

8
00:00:18,620 --> 00:00:20,930
Where n is the length of the cost array.

9
00:00:20,930 --> 00:00:26,780
And initially we will fill this array with the value minus one at every index in this array.

10
00:00:26,780 --> 00:00:33,320
Now in the helper function after the base case, before we go ahead and get into the recursive case,

11
00:00:33,320 --> 00:00:40,160
which is what we have written over here, first we will go and check whether memo at index is not equal

12
00:00:40,160 --> 00:00:41,090
to minus one.

13
00:00:41,090 --> 00:00:43,850
So if memo at index.

14
00:00:44,890 --> 00:00:52,360
Is not equal to minus one, then it would mean that we had already previously computed it and stored

15
00:00:52,360 --> 00:00:53,800
it in the memory.

16
00:00:53,800 --> 00:00:56,500
And that's why it is not equal to minus one.

17
00:00:56,500 --> 00:01:01,990
Because notice initially we had filled every index in the memo array with the value minus one.

18
00:01:01,990 --> 00:01:08,200
So again over here if this is not minus one it is because we have computed and stored a particular value

19
00:01:08,200 --> 00:01:09,520
at that particular index.

20
00:01:09,520 --> 00:01:12,220
And therefore we do not need to recompute this.

21
00:01:12,220 --> 00:01:16,390
But rather we will just return memo at index okay.

22
00:01:16,390 --> 00:01:20,860
Now if this is not the case then these two steps are as it is.

23
00:01:20,860 --> 00:01:23,710
We will go ahead and calculate one and two.

24
00:01:23,710 --> 00:01:27,850
And then before we return over here we will store the value.

25
00:01:27,850 --> 00:01:35,830
So we will say memo at index is equal to whatever we have over here which is math dot min between 1

26
00:01:35,830 --> 00:01:36,760
and 2.

27
00:01:37,240 --> 00:01:38,560
So let us put that over here.

28
00:01:38,560 --> 00:01:41,860
And then we can just return memo at index.

29
00:01:41,860 --> 00:01:42,700
So that's it.

30
00:01:42,700 --> 00:01:48,730
Now notice that we just added a few lines of code to convert the recursive approach to the memoization

31
00:01:48,730 --> 00:01:49,330
approach.

32
00:01:49,330 --> 00:01:53,500
Now let's go ahead and run this code and see if it's passing all the test cases.

33
00:01:54,640 --> 00:01:57,670
And you can see that it's passing all the test cases.