1
00:00:00,810 --> 00:00:07,530
In the previous videos, we have discussed the recursive as well as the memoization approach for solving

2
00:00:07,530 --> 00:00:08,310
the question.

3
00:00:08,310 --> 00:00:10,620
Minimum cost for climbing stairs.

4
00:00:11,040 --> 00:00:16,170
In this video, let's get started with the tabulation or bottom up approach.

5
00:00:16,500 --> 00:00:19,830
Now to discuss this approach, let's take an example.

6
00:00:19,830 --> 00:00:24,510
Let's say the cost array which is given to us is this array over here.

7
00:00:24,510 --> 00:00:30,570
And notice that the length of the array which is given to us over here is equal to eight.

8
00:00:31,190 --> 00:00:38,180
Now, the tabulation approach is all about having a table and storing solutions to subproblems in the

9
00:00:38,180 --> 00:00:38,690
table.

10
00:00:38,690 --> 00:00:44,210
And then we'll use the solutions to subproblems to solve the original problem.

11
00:00:44,210 --> 00:00:54,170
Now for this question, we will need a table which is of length one greater than the length of the cost

12
00:00:54,200 --> 00:00:56,330
array which is given to us.

13
00:00:56,330 --> 00:01:02,780
So over here the length is eight, and the length of the table that we will be using for the tabulation

14
00:01:02,780 --> 00:01:05,180
approach is equal to nine.

15
00:01:05,330 --> 00:01:07,010
Now why is this the case?

16
00:01:07,010 --> 00:01:08,690
Let's try to think about that.

17
00:01:08,690 --> 00:01:15,590
And I'm sure this will become very clear when we discuss what we are actually going to store in these

18
00:01:15,590 --> 00:01:16,340
cells.

19
00:01:16,340 --> 00:01:22,820
So again notice the length of this array is one greater than the length of the input array.

20
00:01:22,820 --> 00:01:32,180
The indices zero up to seven account for the steps which is what is given over here in the cost array.

21
00:01:32,180 --> 00:01:37,580
And then we have one additional cell over here for the destination.

22
00:01:37,580 --> 00:01:44,090
Because remember when we discussed the question we had discussed that the destination is beyond the

23
00:01:44,090 --> 00:01:44,780
input array.

24
00:01:44,780 --> 00:01:46,700
Or we'll have to reach over here.

25
00:01:46,820 --> 00:01:49,820
Or rather it's not about reaching the last index over here.

26
00:01:49,820 --> 00:01:51,800
It's reaching beyond that.

27
00:01:51,800 --> 00:01:59,330
So we need one cell for the destination as well in this table and in each cell in this table over here,

28
00:01:59,330 --> 00:02:06,170
we are going to save the cost required to reach that particular place okay.

29
00:02:06,170 --> 00:02:09,140
The minimum cost to reach that particular index.

30
00:02:09,140 --> 00:02:16,730
For example, the value that we are going to store over here will be the cost required to reach the

31
00:02:16,730 --> 00:02:18,590
step with index four.

32
00:02:18,590 --> 00:02:25,760
Similarly, what we are going to store over here will be the minimum cost required to reach the step

33
00:02:25,760 --> 00:02:26,900
with index seven.

34
00:02:26,900 --> 00:02:35,390
And what we store over here will be the minimum cost required to reach the destination, which is beyond

35
00:02:35,390 --> 00:02:36,410
the steps.

36
00:02:36,410 --> 00:02:41,630
So this is why we need an extra cell in the table over here.

37
00:02:41,630 --> 00:02:50,480
Because our aim is not just to reach the last step, but rather it's to reach beyond the last index.

38
00:02:50,480 --> 00:02:51,620
It's to reach over here.

39
00:02:51,620 --> 00:02:53,660
So that's why we have an extra cell over here.

40
00:02:53,660 --> 00:02:58,670
So we have discussed what we are going to store in each of these cells in this table.

41
00:02:58,670 --> 00:03:00,290
Now let's proceed further.

42
00:03:00,500 --> 00:03:08,420
Remember in the question it was mentioned that we can start at the step with index zero or the step

43
00:03:08,420 --> 00:03:09,650
with index one.

44
00:03:09,650 --> 00:03:17,570
So that means that if we want to reach this step or if we want to reach this step, the cost is zero

45
00:03:17,570 --> 00:03:19,760
because we can just start over there.

46
00:03:19,850 --> 00:03:20,300
Okay.

47
00:03:20,300 --> 00:03:24,560
So if you want to reach this step and we are starting there, then we are already there.

48
00:03:24,560 --> 00:03:27,410
So we did not have to pay anything to reach there.

49
00:03:27,410 --> 00:03:33,980
And remember, what we are storing over here is the cost to reach that place, not to use that particular

50
00:03:33,980 --> 00:03:34,400
step.

51
00:03:34,400 --> 00:03:39,290
So if you want to reach this step and you're starting over here itself, you are already here.

52
00:03:39,290 --> 00:03:41,870
You have not used any step to reach over here.

53
00:03:41,870 --> 00:03:44,240
And that's why the cost is zero.

54
00:03:44,240 --> 00:03:50,540
And therefore we can fill the values at index zero and at index one as zero.

55
00:03:50,540 --> 00:03:53,000
So these are the initial conditions.

56
00:03:53,210 --> 00:03:57,530
Now let's see how we can proceed further and fill this table up.

57
00:03:57,530 --> 00:04:03,260
Because if we can fill this table then we would just have to return the value that we get over here.

58
00:04:03,260 --> 00:04:08,930
Because whatever we are going to fill over here is the minimum cost to reach the destination.

59
00:04:08,930 --> 00:04:11,630
And that's what the question asks of us.

60
00:04:11,630 --> 00:04:14,270
Now, how do we fill this value over here?

61
00:04:14,270 --> 00:04:15,500
Let's discuss that.

62
00:04:15,500 --> 00:04:19,040
Now I can reach this particular step.

63
00:04:19,040 --> 00:04:27,950
That is the step at index two, either by taking two steps from this step or by taking one step from

64
00:04:27,950 --> 00:04:28,820
this step.

65
00:04:28,820 --> 00:04:32,480
So there are two ways of reaching the step with index two.

66
00:04:32,510 --> 00:04:36,230
Now let's compute the cost for these two paths.

67
00:04:36,260 --> 00:04:45,260
Now if I'm going from here to here the total cost involved is zero plus the cost for using the step

68
00:04:45,260 --> 00:04:46,160
at index zero.

69
00:04:46,160 --> 00:04:50,510
Now we have zero over here because the cost to reach over here is zero.

70
00:04:50,510 --> 00:04:56,840
And then we'll have to use this step for which we'll have to pay this amount over here, which is the

71
00:04:56,840 --> 00:04:59,630
value at index zero in the cost array.

72
00:04:59,630 --> 00:05:00,800
And that's equal to one.

73
00:05:00,800 --> 00:05:05,360
So the cost for this path is zero plus one which is equal to one.

74
00:05:05,750 --> 00:05:07,250
What about this path.

75
00:05:07,250 --> 00:05:13,100
The cost for this path over here will be zero plus cost at index one.

76
00:05:13,100 --> 00:05:18,740
Because again we have zero over here because the cost for reaching this index is zero.

77
00:05:18,740 --> 00:05:20,780
And then we are using this step.

78
00:05:20,780 --> 00:05:25,550
So that's why we'll have to pay cost at index one which is two.

79
00:05:25,580 --> 00:05:30,680
So the cost for this path is zero plus two which is equal to two.

80
00:05:30,880 --> 00:05:38,260
And because we are asked to identify the minimum cost for reaching the destination, we are going to

81
00:05:38,260 --> 00:05:43,210
store over here the minimum between these two, which is equal to one.

82
00:05:43,210 --> 00:05:45,730
So I can store this one over here.

83
00:05:45,730 --> 00:05:50,500
Now let's proceed and fill the value at this particular place.

84
00:05:50,500 --> 00:05:54,400
Now again to reach over here I have two possible paths.

85
00:05:54,400 --> 00:06:02,140
I can either start at the step with index one and take two steps, or I can start at the step with index

86
00:06:02,140 --> 00:06:03,670
two and take one step.

87
00:06:03,670 --> 00:06:10,750
Now the cost for this path over here will be zero plus cost at index one, and the cost for this path

88
00:06:10,750 --> 00:06:16,780
will be one, which is this one over here, one plus cost at index two.

89
00:06:16,810 --> 00:06:19,630
Now cost at index one is equal to two.

90
00:06:19,660 --> 00:06:20,980
So that's why this is two.

91
00:06:20,980 --> 00:06:23,410
And cost at index two is equal to one.

92
00:06:23,410 --> 00:06:24,340
So this is one.

93
00:06:24,340 --> 00:06:28,720
So the cost for this path over here is zero plus two which is two.

94
00:06:28,720 --> 00:06:33,250
And the cost for this path over here is one plus one which is equal to two.

95
00:06:33,280 --> 00:06:37,060
Now the minimum between 2 and 2 is two itself.

96
00:06:37,060 --> 00:06:40,510
And therefore I can fill the value two over here.

97
00:06:41,280 --> 00:06:41,940
Okay.

98
00:06:41,940 --> 00:06:48,450
Now let's try to generalize this because I think we have traced the algorithm sufficiently to understand

99
00:06:48,450 --> 00:06:49,950
how this is going to play out.

100
00:06:49,980 --> 00:06:50,370
Right.

101
00:06:50,370 --> 00:06:52,230
So let's write the general case.

102
00:06:52,260 --> 00:06:55,740
Now if I call this array over here min cost.

103
00:06:56,600 --> 00:07:06,410
Then min cost at index, I would be the minimum between the two paths, which I can take to reach the

104
00:07:06,410 --> 00:07:08,090
ith index in this array.

105
00:07:08,120 --> 00:07:17,480
Now the two ways are taking one step from the I minus one step and taking two steps from the I minus

106
00:07:17,480 --> 00:07:18,680
two step.

107
00:07:18,680 --> 00:07:19,130
Okay.

108
00:07:19,160 --> 00:07:25,940
Now for taking one step from I minus one will first have to reach the step with index I minus one.

109
00:07:25,940 --> 00:07:30,200
And that's accounted by this over here min cost at I minus one.

110
00:07:30,200 --> 00:07:32,870
And then we'll have to use that particular step.

111
00:07:32,870 --> 00:07:36,440
And for that we'll have to pay cost at index I minus one.

112
00:07:36,440 --> 00:07:44,360
Similarly for taking two steps from the I minus two step will first have to reach that step.

113
00:07:44,360 --> 00:07:48,110
And for that the cost involved is min cost I minus two.

114
00:07:48,110 --> 00:07:50,180
And then we'll have to use that step.

115
00:07:50,180 --> 00:07:53,000
And for that we'll have to pay cost at I minus two.

116
00:07:53,030 --> 00:07:57,800
So these are the two possible ways for reaching the ith index.

117
00:07:57,800 --> 00:07:59,480
So we'll compute these two.

118
00:07:59,480 --> 00:08:04,940
And then we'll take the minimum of these two and store it at min cost at index I.

119
00:08:04,940 --> 00:08:11,720
So this is how we will iterate over these indices to finally be able to fill the value at this particular

120
00:08:11,720 --> 00:08:12,620
index over here.

121
00:08:12,620 --> 00:08:15,020
And that would be the solution.

122
00:08:15,020 --> 00:08:21,890
So finally we'll just have to return min cost at index n okay.

123
00:08:21,890 --> 00:08:23,450
So I'm just generalizing it.

124
00:08:23,450 --> 00:08:31,160
So if the length of the input array is equal to n then the length of this array which is min cost would

125
00:08:31,160 --> 00:08:32,390
be n plus one.

126
00:08:32,390 --> 00:08:39,110
And the last index over here would be n because this would go from zero to n which is a total of n plus

127
00:08:39,110 --> 00:08:39,830
one cells.

128
00:08:39,830 --> 00:08:42,920
And this index over here is going to be n.

129
00:08:42,920 --> 00:08:46,790
And we'll just have to return min cost at index n.