1
00:00:00,230 --> 00:00:01,370
Welcome back.

2
00:00:01,670 --> 00:00:05,990
Let's start with the intuition required for solving this question.

3
00:00:06,020 --> 00:00:10,100
Now for this, let's take the case where there are three steps.

4
00:00:10,130 --> 00:00:14,090
So if n is equal to three we have three steps.

5
00:00:14,450 --> 00:00:20,480
Now we know that the answer which is expected in this case is three itself because that's a test case

6
00:00:20,480 --> 00:00:21,920
that we had previously written.

7
00:00:21,950 --> 00:00:26,210
Now over here let's make an interesting observation.

8
00:00:26,210 --> 00:00:32,870
Let's say that the number of ways that you can reach the top from this step over here is something that

9
00:00:32,870 --> 00:00:33,440
we know.

10
00:00:33,440 --> 00:00:39,470
And let's say we also know the number of ways in which we can reach the top from this step over here.

11
00:00:39,500 --> 00:00:46,550
Now, if we know that, then the number of ways of reaching the top or the answer to this problem would

12
00:00:46,550 --> 00:00:49,850
be the sum of those two values.

13
00:00:50,360 --> 00:00:51,560
Now why is that the case?

14
00:00:51,590 --> 00:00:53,540
Let's think about it for this.

15
00:00:53,540 --> 00:00:57,680
Let me number the steps over here as one, two and three.

16
00:00:57,680 --> 00:01:00,620
And let's say that this over here is equal to b.

17
00:01:00,620 --> 00:01:03,830
So there are b ways of reaching the top from step one.

18
00:01:03,830 --> 00:01:07,730
And there are a ways of reaching the top from step number two.

19
00:01:07,760 --> 00:01:16,790
Now notice that for each of the b ways which we have identified over here, we can reach the top without

20
00:01:16,790 --> 00:01:23,870
going to step number two in just one way, which is directly going from step one to step three.

21
00:01:23,900 --> 00:01:31,190
Similarly, for each of the A ways in which we were able to reach step number two, we are able to reach

22
00:01:31,190 --> 00:01:34,070
the top by just taking one step.

23
00:01:34,070 --> 00:01:42,830
So this means that when we identify that we can reach this step in b ways, we have actually identified

24
00:01:42,830 --> 00:01:49,790
the number of ways in which we reach over here and reach the top without going to step number two.

25
00:01:49,820 --> 00:01:51,650
So that's what actually B is.

26
00:01:52,070 --> 00:01:58,580
Similarly a ways, which is the number of ways of reaching this step, is actually the number of ways

27
00:01:58,580 --> 00:02:01,280
of reaching this step and reaching the top.

28
00:02:01,280 --> 00:02:07,160
So that's why we can say that the number of ways of reaching the top is just B plus a.

29
00:02:07,460 --> 00:02:09,170
Now let's generalize this.

30
00:02:09,170 --> 00:02:12,170
Let's say that instead of three this is n.

31
00:02:12,620 --> 00:02:14,630
Then this would be n minus one.

32
00:02:14,630 --> 00:02:16,730
And this would be n minus two.

33
00:02:18,550 --> 00:02:20,290
Let's make some space over here.

34
00:02:20,290 --> 00:02:27,220
So what we have seen is the number of ways of reaching step number three is equal to the number of ways

35
00:02:27,220 --> 00:02:32,440
of reaching step number one, plus the number of ways of reaching step number two.

36
00:02:32,440 --> 00:02:41,110
Or in other words, the number of ways of reaching step number n is equal to the number of ways of reaching

37
00:02:41,110 --> 00:02:47,650
step number n minus one, plus the number of ways of reaching step number n minus two.

38
00:02:47,680 --> 00:02:55,630
So notice that what we have over here is the same thing that we had for the Fibonacci question, where

39
00:02:55,630 --> 00:03:02,890
it was given that f of n is equal to f of n minus one plus f of n minus two.

40
00:03:05,070 --> 00:03:12,090
So that's why this question is actually the same Fibonacci question put forth in a different way.

41
00:03:12,090 --> 00:03:15,930
Or it's an application of the Fibonacci question.

42
00:03:16,290 --> 00:03:22,500
So you can solve this question using the same approach that we have discussed for the Fibonacci question.

43
00:03:22,500 --> 00:03:27,270
And I would highly recommend that you first write the recursive solution.

44
00:03:27,270 --> 00:03:29,040
Then you can memorize it.

45
00:03:29,040 --> 00:03:35,640
And after that write the tabulation approach as well as the space optimized tabulation approach.

46
00:03:35,640 --> 00:03:43,410
So this is an awesome question to practice on your own and to solidify your learning and remember the

47
00:03:43,410 --> 00:03:49,890
time and space complexity of these solutions that you're going to write will be the same as what we

48
00:03:49,890 --> 00:03:55,440
have discussed for these respective approaches when we discussed the Fibonacci question.