1
00:00:01,560 --> 00:00:02,280
Hi, everyone.

2
00:00:02,310 --> 00:00:06,790
So in this video, we are going to discuss about this question, climbing stairs.

3
00:00:07,860 --> 00:00:14,340
So in this question, what we have given to us is we are standing at the ground floor and we want to

4
00:00:14,340 --> 00:00:15,270
reach to the top.

5
00:00:17,560 --> 00:00:24,380
So these are insteps steps, these are steps and I want to rise to the top, so it is given willing

6
00:00:24,430 --> 00:00:26,860
to take any steps to reach to the top.

7
00:00:27,790 --> 00:00:32,180
And the condition is we can either climb one step or two step.

8
00:00:32,560 --> 00:00:40,590
So either I will take a jump of one or I will take a jump of two from each step and we need to return.

9
00:00:40,600 --> 00:00:43,630
How many distinct ways are there to climb to the top?

10
00:00:44,650 --> 00:00:49,750
So this is the question and it's a pretty simple question we can easily solved with the help of recursion.

11
00:00:50,350 --> 00:00:51,520
So see.

12
00:00:53,080 --> 00:01:01,240
Let me draw this diagram so I want to reach this step, and this is and minus one step.

13
00:01:01,280 --> 00:01:04,599
This is and my is step and and my next steps.

14
00:01:05,830 --> 00:01:09,950
So either I can take a jump of two or one.

15
00:01:10,510 --> 00:01:16,090
So basically I can reach this step and from and minus one by taking a step of one.

16
00:01:16,330 --> 00:01:20,970
Or I can reach this and step by taking a step of two from and minus two.

17
00:01:21,640 --> 00:01:22,020
Right.

18
00:01:22,510 --> 00:01:29,350
So the number of ways, the number of ways to reach and step is basically either you can come from and

19
00:01:29,350 --> 00:01:33,190
minus one step or you can come from and minus two.

20
00:01:33,700 --> 00:01:35,490
So that will be our course relation.

21
00:01:36,520 --> 00:01:42,820
I'm explaining again, I want to reach here so either I can come from and minus one by taking a step

22
00:01:42,820 --> 00:01:47,590
of one or I can count from and minus two by taking a step of two.

23
00:01:48,130 --> 00:01:52,810
So a number of ways to reach and will be the number of ways to reach and minus one, plus the number

24
00:01:52,810 --> 00:01:56,200
of these number of distinct ways to reach and minus two.

25
00:01:56,890 --> 00:02:01,540
So that will be our recursive relation and what will be our best case.

26
00:02:02,170 --> 00:02:03,430
So best case is.

27
00:02:05,700 --> 00:02:09,280
This is ground this is step one and this is ground level.

28
00:02:09,570 --> 00:02:12,620
So how many number of ways to reach at this step?

29
00:02:12,900 --> 00:02:13,880
Only one, right?

30
00:02:14,550 --> 00:02:16,370
I can take a jump of only one.

31
00:02:16,770 --> 00:02:18,930
So we know what is half of one.

32
00:02:18,930 --> 00:02:20,430
Half of one is one.

33
00:02:21,490 --> 00:02:27,400
Right, so we know the reconciliation, we know the base case, let's start writing the code.

34
00:02:29,880 --> 00:02:31,980
So the cold is going to be pretty simple.

35
00:02:32,010 --> 00:02:39,480
We are going to use recursion for solving this problem, so we will return integer number of distinct

36
00:02:39,480 --> 00:02:40,710
ways to climb to the top.

37
00:02:41,340 --> 00:02:44,790
Let's say the name of the function is count steps.

38
00:02:51,180 --> 00:03:00,300
So first, let's talk about the base case, so base cases, if the value of an is one, then how many

39
00:03:00,300 --> 00:03:00,600
steps?

40
00:03:00,600 --> 00:03:01,920
I need to take one step.

41
00:03:01,920 --> 00:03:10,020
Right, so they are done when similarly, if the value of any zero you are standing at the ground level,

42
00:03:10,020 --> 00:03:11,640
then how many steps to take?

43
00:03:13,080 --> 00:03:13,520
None.

44
00:03:13,650 --> 00:03:14,170
Right.

45
00:03:14,190 --> 00:03:16,440
So there is one way we need to return.

46
00:03:16,440 --> 00:03:17,850
How many distinct ways?

47
00:03:18,630 --> 00:03:19,380
So there is one.

48
00:03:19,380 --> 00:03:20,590
We do not do anything.

49
00:03:20,610 --> 00:03:21,840
So there is one way, right.

50
00:03:24,920 --> 00:03:27,860
Now, our caste relation was our answer was.

51
00:03:30,650 --> 00:03:41,370
No steps to reach and minus one plus number of steps to reach and minus two.

52
00:03:42,950 --> 00:03:45,230
And now we just need to call this function.

53
00:03:50,300 --> 00:03:56,870
So they don't count steps and and and that said, this is going to be the complete college right now

54
00:03:57,110 --> 00:03:58,000
and then I will submit.

55
00:04:01,830 --> 00:04:02,670
So summit.

56
00:04:03,960 --> 00:04:11,070
So since this is recursive cold, we are going to encounter a time limit exceeded,

57
00:04:13,950 --> 00:04:22,200
right, because this is recursive cold and we can easily convert this recursive code into a deep code,

58
00:04:22,200 --> 00:04:23,950
which we are going to do in our next video.

59
00:04:24,240 --> 00:04:28,410
And if you click here, we can see how many test cases our code is passing.

60
00:04:28,830 --> 00:04:37,140
So out of 45, if we have passed 21 test cases, our code is failing for the remaining test cases because

61
00:04:37,140 --> 00:04:37,890
of time limit.

62
00:04:38,490 --> 00:04:43,790
So we NextRadio, what they are going to do is we are going to convert the second resolution into DEPI

63
00:04:43,830 --> 00:04:44,370
solution.

64
00:04:45,270 --> 00:04:45,770
Right.

65
00:04:46,230 --> 00:04:48,670
So we will do that in our next video.

66
00:04:49,080 --> 00:04:50,780
So this is a tremendous device.

67
00:04:50,790 --> 00:04:52,240
I will see you in the next one.

68
00:04:52,530 --> 00:04:53,040
Thank you.

