1
00:00:00,290 --> 00:00:05,420
We have another interesting question over here, which is called climbing stairs.

2
00:00:05,450 --> 00:00:09,800
So the question reads you are climbing a staircase.

3
00:00:09,800 --> 00:00:13,250
It takes N steps to reach the top.

4
00:00:13,700 --> 00:00:17,780
Each time you can either climb 1 or 2 steps.

5
00:00:18,140 --> 00:00:22,130
In how many distinct ways can you climb to the top?

6
00:00:22,130 --> 00:00:25,460
So this is the question and we are given an example.

7
00:00:25,460 --> 00:00:27,650
So if n is equal to two.

8
00:00:27,680 --> 00:00:29,600
So you have two steps over here.

9
00:00:29,600 --> 00:00:34,040
And if this is the case there are two ways of reaching the top.

10
00:00:34,040 --> 00:00:37,370
So you could take one step and again one step.

11
00:00:37,370 --> 00:00:38,540
So that's way one.

12
00:00:38,540 --> 00:00:42,290
And you could take two steps together and reach the top.

13
00:00:42,290 --> 00:00:43,250
So that's way two.

14
00:00:43,280 --> 00:00:48,530
So there are two ways of reaching the top if there are just two steps.

15
00:00:49,010 --> 00:00:50,870
So this is the question at hand.

16
00:00:50,900 --> 00:00:52,880
Now let's just discuss this a bit.

17
00:00:52,880 --> 00:00:57,860
So it says each time you can either climb 1 or 2 steps.

18
00:00:57,860 --> 00:01:03,530
And we need to find the distinct number of ways in which you can climb to the top.

19
00:01:03,530 --> 00:01:08,810
So let's say you have a few steps over here and you're starting over here.

20
00:01:09,200 --> 00:01:16,190
Now in the question it's mentioned that you can either take one step or you can take two steps at a

21
00:01:16,190 --> 00:01:16,790
time.

22
00:01:16,790 --> 00:01:21,080
Now how do we identify that this is a dynamic programming question.

23
00:01:21,080 --> 00:01:22,550
So let's think about that.

24
00:01:22,550 --> 00:01:28,190
So to identify that notice that over here you have choices in place.

25
00:01:28,190 --> 00:01:32,000
You can either take one step or you can take two steps.

26
00:01:32,000 --> 00:01:36,320
So this is a clue that you could probably use dynamic programming.

27
00:01:36,320 --> 00:01:40,130
Because when you have choices at hand we can use recursion.

28
00:01:40,130 --> 00:01:47,870
Also do notice that you will have overlapping subproblems because these are actually two branches right.

29
00:01:47,870 --> 00:01:49,100
So these are two branches.

30
00:01:49,100 --> 00:01:52,580
So this branch is when you start with taking one step.

31
00:01:52,580 --> 00:01:55,670
And this branch over here starts by taking two steps.

32
00:01:55,670 --> 00:02:01,790
Now let's say in both these processes you will reach this step over here.

33
00:02:02,850 --> 00:02:07,710
And then from this step, let's say there are k ways to reach to the top.

34
00:02:07,710 --> 00:02:13,920
So over here notice that reaching this step will happen in both these branches.

35
00:02:13,920 --> 00:02:18,750
And then you would have to calculate k twice if you're not using dynamic programming.

36
00:02:18,750 --> 00:02:21,360
So you have overlapping subproblems.

37
00:02:21,360 --> 00:02:25,680
So again in this branch when you're taking two steps you directly reaching over here.

38
00:02:25,680 --> 00:02:31,650
And when you're taking one steps there is a possibility that the next step is also going to be one step.

39
00:02:31,650 --> 00:02:32,880
And you will reach over here.

40
00:02:32,880 --> 00:02:39,240
So the subproblem of finding the number of ways in which you can reach to the top from this step over

41
00:02:39,240 --> 00:02:42,240
here will happen in both the branches.

42
00:02:42,240 --> 00:02:45,330
So there are overlapping subproblems.

43
00:02:45,330 --> 00:02:51,630
So this is a strong indication that we can use dynamic programming to solve this question.

44
00:02:51,630 --> 00:02:58,830
In fact, we will see how this question over here is an application of the Fibonacci question that we

45
00:02:58,830 --> 00:03:00,090
have previously discussed.

46
00:03:00,390 --> 00:03:06,420
So we have understood the question and we have also identified that this is a dynamic programming question.

47
00:03:06,420 --> 00:03:09,600
Now let's take a look at a few interesting test cases.

48
00:03:09,750 --> 00:03:16,710
As part of the question, we were given an example that if n is equal to two, the output required is

49
00:03:16,710 --> 00:03:20,430
two itself, or there are two distinct ways of reaching the top.

50
00:03:20,430 --> 00:03:24,030
And again these are the two ways you could take one step and one step.

51
00:03:24,030 --> 00:03:27,330
Or you can directly take two steps to reach to the top.

52
00:03:27,630 --> 00:03:31,920
Now if n is equal to three, the output again has to be three.

53
00:03:31,920 --> 00:03:34,260
Because notice if you have three steps.

54
00:03:34,260 --> 00:03:37,890
This is one way which is taking one step at a time.

55
00:03:37,890 --> 00:03:43,110
Then you could take one step initially and then take two steps over here.

56
00:03:43,110 --> 00:03:44,550
So this is one more way.

57
00:03:44,550 --> 00:03:49,110
And you could take two steps initially and then take one more step.

58
00:03:49,110 --> 00:03:53,970
And again the first one that we discussed was taking one steps at every point.

59
00:03:53,970 --> 00:03:57,270
So these are the three ways of reaching the top.

60
00:03:57,270 --> 00:04:03,690
If there are just three steps now if there is just one step, then there is just one way of reaching

61
00:04:03,690 --> 00:04:05,490
the top by taking one step.

62
00:04:05,490 --> 00:04:08,340
So again, these are a few interesting test cases.

63
00:04:08,340 --> 00:04:13,140
Now in the next video let's discuss how you can easily solve this question.