1
00:00:00,050 --> 00:00:04,760
Let's now write the tabulation approach for solving the minimum cost climbing stairs.

2
00:00:04,760 --> 00:00:05,300
Question.

3
00:00:05,300 --> 00:00:08,150
So again we are given this cost array over here.

4
00:00:08,150 --> 00:00:12,530
Now let's say let n is equal to cost dot length.

5
00:00:14,550 --> 00:00:24,060
Okay, now we would need a DP array, and in the DP array, every value at every index is going to represent

6
00:00:24,060 --> 00:00:28,470
the cost required to reach that particular index.

7
00:00:28,500 --> 00:00:34,590
Now because the question is about reaching beyond the last step, like that's something that we have

8
00:00:34,590 --> 00:00:35,610
previously discussed.

9
00:00:35,610 --> 00:00:38,820
Like for example, let's say the cost array has three elements.

10
00:00:38,820 --> 00:00:43,950
So that would mean there is a step at index zero, step at index one and step at index two.

11
00:00:43,950 --> 00:00:47,730
And the aim is to get beyond the step at index two.

12
00:00:47,760 --> 00:00:48,120
Okay.

13
00:00:48,120 --> 00:00:53,370
So that's why the length of this DP array is going to be n plus one.

14
00:00:53,370 --> 00:00:55,980
Because we just don't need to reach the last step.

15
00:00:55,980 --> 00:00:58,290
We need to reach beyond it okay.

16
00:00:58,290 --> 00:01:05,160
And at every index over here in the DP array we are going to store the cost of reaching that particular

17
00:01:05,160 --> 00:01:05,700
step.

18
00:01:05,700 --> 00:01:07,800
And the size is n plus one.

19
00:01:07,800 --> 00:01:12,600
And initially we will fill each cell in this array with the value zero.

20
00:01:12,600 --> 00:01:18,150
Now again over here notice the size or the length of this array is n plus one.

21
00:01:18,150 --> 00:01:22,170
And finally we will be just returning dp at n.

22
00:01:22,530 --> 00:01:31,020
Again the steps range from zero to n minus one, and dp at n would be the cost for reaching beyond the

23
00:01:31,020 --> 00:01:31,830
last step.

24
00:01:31,830 --> 00:01:34,020
And that's what we need to find out okay.

25
00:01:34,290 --> 00:01:36,120
So let's write that over here as well.

26
00:01:36,120 --> 00:01:41,070
So finally we will just be returning DP at N okay.

27
00:01:41,070 --> 00:01:45,030
Now to proceed we can say that DP at zero.

28
00:01:45,780 --> 00:01:51,420
Is equal to zero and dp at one is equal to zero.

29
00:01:51,750 --> 00:01:58,140
Now this is the case because in the question it's mentioned that we can start either at the first or

30
00:01:58,140 --> 00:01:59,700
the second step okay.

31
00:01:59,700 --> 00:02:04,800
That is we can either start at the step with index zero or the step with index one.

32
00:02:04,800 --> 00:02:10,050
And therefore there is no cost associated with reaching those two particular steps.

33
00:02:10,050 --> 00:02:21,930
And again remember in this DP array over here we are storing the cost for reaching the step with a particular

34
00:02:21,930 --> 00:02:22,620
index.

35
00:02:24,700 --> 00:02:31,000
Like for example, at DP at zero we are storing the cost for reaching the step with index zero.

36
00:02:31,030 --> 00:02:37,510
Similarly, dp at index five, for example, would be the cost for reaching the step with index five.

37
00:02:37,690 --> 00:02:41,800
Okay, so dp at zero is zero and dp at one is one.

38
00:02:41,800 --> 00:02:46,120
And now we would need to iterate from two up to n.

39
00:02:46,120 --> 00:02:54,370
So I can say for let I is equal to two I less than equal to n I plus plus okay.

40
00:02:54,460 --> 00:03:03,580
And for each of these cases I have to calculate the cost for reaching that particular index either by

41
00:03:03,580 --> 00:03:06,370
taking one step or two steps.

42
00:03:06,370 --> 00:03:09,130
So again let me write this out and it will become clear.

43
00:03:09,130 --> 00:03:24,160
So let's have two variables cost to come from one step back and cost to come from two steps.

44
00:03:25,230 --> 00:03:26,100
Back.

45
00:03:26,430 --> 00:03:34,920
Okay, now the cost for reaching this particular index, the step with this particular index by taking

46
00:03:34,920 --> 00:03:43,410
one step would be cost at I minus one plus depee at I minus one.

47
00:03:44,380 --> 00:03:44,920
Right.

48
00:03:44,920 --> 00:03:46,090
So why is this the case?

49
00:03:46,090 --> 00:03:51,070
Because this would be the cost for reaching the step with index I minus one.

50
00:03:51,070 --> 00:03:54,940
And we would have to use that step and take one step.

51
00:03:54,940 --> 00:03:58,660
So whenever we are using a step we'd have to pay this price.

52
00:03:58,660 --> 00:03:59,020
Right.

53
00:03:59,020 --> 00:04:06,280
So that's why the cost to come to the index I by taking one step would be cost.

54
00:04:06,280 --> 00:04:09,130
And I minus one plus d p at I minus one.

55
00:04:09,130 --> 00:04:16,660
Similarly, the cost to reach the step with index I by taking two steps from these steps, which are

56
00:04:16,660 --> 00:04:24,670
two steps previous to it would be cost at I minus two plus d p at I minus two.

57
00:04:25,390 --> 00:04:27,370
Okay, and then d p at.

58
00:04:27,370 --> 00:04:34,090
I would be the minimum between these two because we are finding the minimum cost of climbing the stairs.

59
00:04:34,090 --> 00:04:44,350
So DP at I would be the minimum between cost to come from one step and cost to come from two steps back.

60
00:04:45,040 --> 00:04:45,610
Okay.

61
00:04:46,000 --> 00:04:51,400
And finally over here we have already written once we are done with this, once we have iterated through

62
00:04:51,400 --> 00:04:57,130
the values from two up to n, we would have calculated d p at n, and then we will just return dp at

63
00:04:57,130 --> 00:04:57,430
n.

64
00:04:57,430 --> 00:05:02,770
And again remember n is beyond the last step which has the index n minus one.

65
00:05:02,770 --> 00:05:08,110
So when we reach the index n it means that we have gone beyond the last step.

66
00:05:08,110 --> 00:05:10,510
And that's what the question asks us to find.

67
00:05:10,510 --> 00:05:12,640
So we can just return dp at n.

68
00:05:12,640 --> 00:05:14,200
And this should solve the question.

69
00:05:14,200 --> 00:05:18,430
Now let's go ahead and run this code and see if it's passing all the test cases.

70
00:05:19,000 --> 00:05:20,620
And you can see that it's working.

71
00:05:20,620 --> 00:05:22,240
It's passing all the test cases.