1
00:00:00,230 --> 00:00:06,500
In the previous videos, we have already discussed the recursive approach for solving the minimum cost

2
00:00:06,500 --> 00:00:07,370
climbing stairs.

3
00:00:07,370 --> 00:00:08,000
Question.

4
00:00:08,030 --> 00:00:12,020
Now over here, let's see how we can memorize this.

5
00:00:12,020 --> 00:00:17,060
And again remember the memoization approach is also called the top down approach.

6
00:00:17,060 --> 00:00:20,210
And this will significantly improve the time complexity.

7
00:00:20,210 --> 00:00:24,890
And the good news is that we can do this by just adding a few lines of code.

8
00:00:24,920 --> 00:00:28,220
Now to discuss this approach, let's take an example.

9
00:00:28,220 --> 00:00:31,310
Let's say this is the cost array which is given to us.

10
00:00:31,310 --> 00:00:37,790
And over here we notice that we have the indices starting at index zero going up to index seven.

11
00:00:38,060 --> 00:00:44,720
Now in the recursive approach, because we did implement the recursive solution starting at index zero

12
00:00:44,720 --> 00:00:46,580
and going to the last index.

13
00:00:46,580 --> 00:00:53,090
Remember we had discussed that we have to calculate both cost from zero and cost from one.

14
00:00:53,090 --> 00:00:55,760
And then we would return the minimum among these two.

15
00:00:55,760 --> 00:01:01,160
And this is the case because we can either start at index zero or start at index one.

16
00:01:01,160 --> 00:01:05,210
Now let's quickly draw the recursive tree for one of them.

17
00:01:05,210 --> 00:01:11,780
And this is just to see that there are in fact overlapping subproblems, which makes a strong case for

18
00:01:11,780 --> 00:01:13,250
memoization techniques.

19
00:01:13,250 --> 00:01:13,640
Right.

20
00:01:13,640 --> 00:01:16,340
So we start at cost from zero.

21
00:01:16,340 --> 00:01:23,030
And then we would call cost from one and cost from two in the two branches because we can either take

22
00:01:23,030 --> 00:01:24,980
one step or two steps.

23
00:01:24,980 --> 00:01:31,370
Now if we reach the step at index one again we would have two branches cost from index two and cost

24
00:01:31,370 --> 00:01:32,210
from index three.

25
00:01:32,210 --> 00:01:35,210
This is taking one step and this is taking two steps.

26
00:01:35,210 --> 00:01:36,830
And it goes on in this manner.

27
00:01:36,830 --> 00:01:43,340
Now over here, if we reach the step at index two we would again have two branches and cost from index

28
00:01:43,340 --> 00:01:43,610
three.

29
00:01:43,610 --> 00:01:47,750
This is the case where we take one step and we would call cost from index four.

30
00:01:47,780 --> 00:01:50,240
This is the case where we take two steps.

31
00:01:50,240 --> 00:01:57,560
Now over here notice that we are calling cost from index two over here as well as over here.

32
00:01:57,560 --> 00:02:00,680
So we have overlapping subproblems.

33
00:02:00,680 --> 00:02:07,700
Similarly when it comes to cost from index three notice that we have it over here as well as over here.

34
00:02:07,700 --> 00:02:11,090
And this makes a strong case for memoization.

35
00:02:11,090 --> 00:02:17,540
Because if we just store these values when we compute them we could have avoided computing this again.

36
00:02:17,540 --> 00:02:17,900
Right.

37
00:02:17,900 --> 00:02:22,970
We could have just returned the value because we have already computed it probably over here.

38
00:02:23,390 --> 00:02:31,370
Now in this question we can use a hash map or a simple array for storing the costs that we are computing.

39
00:02:31,370 --> 00:02:34,100
And again, let's say we are just doing it with an array.

40
00:02:34,100 --> 00:02:35,660
So how would it look like.

41
00:02:35,660 --> 00:02:43,370
So because we have seven indices over here, we would need seven places in this array where we are going

42
00:02:43,370 --> 00:02:45,050
to store the costs.

43
00:02:45,230 --> 00:02:50,240
And then at every place we are just going to store the value that we get over here.

44
00:02:50,240 --> 00:02:55,250
So cost from zero would be stored over here, cost from one would be stored over here.

45
00:02:55,250 --> 00:02:56,810
And it goes on in this manner.

46
00:02:56,810 --> 00:03:02,330
Now again we are not going from 0 to 1 etc. like we would do in the case of tabulation.

47
00:03:02,330 --> 00:03:07,940
What we are doing over here is whenever we get a value, like for example, let's say there were just

48
00:03:07,940 --> 00:03:09,170
four elements.

49
00:03:09,170 --> 00:03:15,200
So let's say this is the cost array which is given to us now over here when we come to cost from index

50
00:03:15,200 --> 00:03:15,620
three.

51
00:03:15,620 --> 00:03:16,010
Right.

52
00:03:16,010 --> 00:03:17,360
So that's the last element.

53
00:03:17,360 --> 00:03:21,170
So there would be just one way of reaching the top right.

54
00:03:21,170 --> 00:03:22,610
And we could get the value.

55
00:03:22,610 --> 00:03:29,300
So in this case if this is the input array cost from index three would be taking one step from this

56
00:03:29,300 --> 00:03:30,080
step over here.

57
00:03:30,080 --> 00:03:31,610
And the cost for that is three.

58
00:03:31,610 --> 00:03:31,910
Right.

59
00:03:31,910 --> 00:03:35,780
So when we compute it we are just going to directly store it over here.

60
00:03:36,200 --> 00:03:39,530
Let's say hypothetically in this example it's three right.

61
00:03:39,530 --> 00:03:45,680
So if this was the cost array and the cost from going from this index to the top would be three.

62
00:03:45,680 --> 00:03:47,270
So we would just store it over here.

63
00:03:47,270 --> 00:03:54,080
Or if this itself is the array which is given to us, we can compute the cost for reaching the top from

64
00:03:54,080 --> 00:03:54,860
index seven.

65
00:03:54,860 --> 00:03:58,340
And that would be just one because we just take one step right.

66
00:03:58,340 --> 00:03:59,420
So this is the last step.

67
00:03:59,420 --> 00:04:02,420
So we would directly compute it and store it over here.

68
00:04:02,420 --> 00:04:09,350
So whenever we are able to compute the cost for going from a particular index to the top, whenever

69
00:04:09,350 --> 00:04:12,860
we get the value, we will just store it in this array.

70
00:04:12,860 --> 00:04:19,670
And then in any branch or in any recursive call, before we go ahead and compute the cost for going

71
00:04:19,670 --> 00:04:25,430
from that particular index to the top, we will check whether we had previously computed the cost,

72
00:04:25,430 --> 00:04:28,640
because if we did compute it, we would have stored it in this array.

73
00:04:28,640 --> 00:04:32,510
And we will just retrieve it and return it without recomputing.

74
00:04:32,510 --> 00:04:34,730
So that's the memoization approach.

75
00:04:34,730 --> 00:04:41,270
And again, as we always do with memoization over here, also, we will just initially fill all these

76
00:04:41,270 --> 00:04:42,980
cells with minus one.

77
00:04:42,980 --> 00:04:48,080
And that will help us to check whether we have computed the value previously or not.

78
00:04:48,080 --> 00:04:55,010
Because whenever we have cost from a particular index, we will check whether the value at that particular

79
00:04:55,010 --> 00:04:58,010
index in this array over here is minus one or not.

80
00:04:58,010 --> 00:04:59,660
And if we see that it's not.

81
00:04:59,790 --> 00:05:00,510
Minus one.

82
00:05:00,510 --> 00:05:06,390
We will not go ahead with any computations, but rather we would just retrieve that value and return

83
00:05:06,390 --> 00:05:06,660
it.

84
00:05:06,660 --> 00:05:13,410
On the other hand, if we see that the value at that particular index in this array is minus one, then

85
00:05:13,410 --> 00:05:19,500
we will go down the recursive tree to compute its value, and before we return it, we will always store

86
00:05:19,500 --> 00:05:21,240
it in this array over here.

87
00:05:21,240 --> 00:05:24,000
So that's the memoization approach for solving this.