Climbing Stairs (LeetCode 70) | Full solution with animations | Dynamic Easy | Study Algorithms
Climbing Stairs (LeetCode 70) | Full solution with animations | Dynamic Easy | Study Algorithms
Given a staircase with n steps, we need to find the total number of distinct ways to climb it by taking 1 or 2 steps at a time. Sure, this can be done by a brute force method and finding all the possibilities, but there is a really easy way to understand this. This video shows how you can form building blocks and ultimately arrive at a very efficient solution. To make things easy, there is also a dry run of code in JAVA.
Chapters:
00:00 - Intro
01:36 - Problem statement and description
04:51 - Brute Force Method
07:28 - How to understand and attack
09:41 - Finding an efficient solution
12:19 - Dry-run of Code
14:45 - Final Thoughts
Actual problem on LeetCode: https://leetcode.com/problems/climbin…
📚 Links to topics I talk about in the video:
Dynamic Programming: • Dynamic Programming easy to understan…
Brute Force Solution: • Brute Force algorithms with real life…
What is Big O?: • Big O Notation Simplified to the MAX …
📘 A text based explanation is available at: https://studyalgorithms.com
Code on Github: https://github.com/nikoo28/java-solut…
Test-cases on Github: https://github.com/nikoo28/java-solut…
📖 Reference Books:
Starting Learn to Code: https://amzn.to/36pU0JO
Favorite book to understand algorithms: https://amzn.to/39w3YLS
Favorite book for data structures: https://amzn.to/3oAVBTk
Get started for interview preparation: https://amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: https://www.buymeacoffee.com/studyalg…
🎥 My Recording Gear:
Recording Light: https://amzn.to/3pAqh8O
Microphone: https://amzn.to/2MCX7qU
Recording Camera: https://amzn.to/3alg9Ky
Tablet to sketch and draw: https://amzn.to/3pM6Bi4
Surface Pen: https://amzn.to/3pv6tTs
Laptop to edit videos: https://amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: https://www.facebook.com/studyalgos
Follow on Twitter at: https://www.twitter.com/studyalgorithms
Follow on Tumblr at: https://studyalgos.tumblr.com/
Subscribe to RSS feeds: https://studyalgorithms.com/feed/
Join fan mail: http://eepurl.com/g9Dadv
#leetcode #programming #interview
Content
0.24 -> this question could be the first
2.32 -> question that you solve upon dynamic
4.08 -> programming wait wait wait don't be
6.64 -> scared by listening the name dynamic
8.32 -> programming
9.599 -> if you follow step by step and try to
12.559 -> visualize the question
14.08 -> dynamic programming could be really
15.839 -> simple
16.8 -> you just need to follow the instructions
19.119 -> and try to visualize the problem in your
21.199 -> mind
22.4 -> as per the problem statement you are
24.56 -> given a staircase with n steps
28.08 -> at a time you can either take one step
30.48 -> or two steps at a time
32.48 -> and you need to determine the total
34.88 -> number of distinct ways in which you can
37.2 -> climb the staircase
39.28 -> i will show you visually and
40.879 -> diagrammatically how you can approach
43.2 -> this problem very very easily
45.52 -> hello friends welcome back to my channel
48 -> a place where we explore the life of
50 -> technology and make programming fun and
52.079 -> easy to learn
53.44 -> first i will explain you the problem
55.44 -> statement and we will look at some
57.199 -> sample test cases
59.12 -> next we will try to come up with a brute
61.76 -> force solution to the problem and see
64 -> why this is not a feasible solution
66.88 -> going forward i will show you how to
69.52 -> attack this problem i will show you how
72.159 -> you can visualize it and how you
74.32 -> ultimately build a solution
76.4 -> so that way you will understand the
79.2 -> basic concepts of dynamic programming
81.68 -> and how does memoization work
84.479 -> going forward we will also do a dry run
86.88 -> of the code so that all of this sticks
89.04 -> in your mind forever so without further
91.6 -> ado let's get started
97.36 -> let us first try to make sure that we
99.6 -> are understanding the problem statement
101.2 -> correctly
102.56 -> in this problem you have to climb a
105.04 -> staircase right
106.96 -> and this staircase has total of m steps
111.439 -> you need to find out the total number of
113.759 -> distinct waves in which you can climb
116.24 -> the staircase
117.68 -> so what does that actually mean
120.079 -> let us look at two sample test cases
122.96 -> in our first test case you can see that
125.28 -> the value of n is two
127.68 -> this means that your staircase will have
130.56 -> two steps to climb correct
133.36 -> and how can you climb the staircase
136.16 -> so
136.879 -> one way to climb the staircase would be
139.44 -> you can take one step and then another
141.84 -> step
142.72 -> right
143.52 -> and then you would reach the top
145.599 -> so you took one step and then you took
147.92 -> one step again
149.599 -> so this is one way
151.599 -> what is the other way that you can climb
153.2 -> this staircase
154.48 -> you can also take two steps at a time
156.959 -> right so what this person can do is he
159.519 -> can directly go over to the second step
162.319 -> and this is once again one more way to
165.12 -> climb the staircase
167.04 -> so what did you do you just took two
169.12 -> steps at a time right
171.519 -> and there is no other way that you can
173.68 -> climb the staircase
175.2 -> so this gives you a total of two ways to
178.319 -> climb the staircase
180.08 -> and hence the answer to this test case
182.319 -> is two
184.8 -> because you can climb the staircase in 2
187.2 -> different ways
189.12 -> similarly let us look at another test
191.519 -> case
192.72 -> this time the value of n is 3
195.2 -> that means this staircase will have
197.44 -> three steps right
199.28 -> and here you are you want to climb the
201.68 -> staircase how can you do it
204.239 -> one way would be very simple right you
206.239 -> climb one step at a time so one two and
208.959 -> three you reach the top
211.28 -> so this is one way
214.319 -> next how else can you climb this
216.4 -> staircase you can also take two steps at
218.959 -> a time right
220.159 -> so what if i take two steps now and i'm
222.72 -> remaining with one more step so i take
224.799 -> one step more once again i am at the top
228.159 -> so the path i followed is two steps and
231.44 -> then one step
233.92 -> you have to find all the different ways
236.159 -> correct
237.12 -> so you can approach this problem one
239.84 -> more way what you can do is you can take
242.239 -> one step at a time and then you can take
244.4 -> two steps
245.68 -> once again you will climb the staircase
248.319 -> so this is one more way you can climb
250.48 -> the staircase so you took one step and
253.12 -> then two steps at a time
256.16 -> notice that there is no other way that
258.479 -> you can climb the staircase if you try
260.799 -> to do two steps and then two steps you
262.88 -> cannot reach anywhere right since this
265.28 -> staircase only has a total of three
267.84 -> stairs right
269.68 -> so for test case number two three would
272.08 -> be your answer because you can climb
274.4 -> this staircase in a total number of
277.04 -> three different ways
279.36 -> now if this problem statement is clear
281.52 -> to you feel free to try it out on your
283.52 -> own
284.479 -> otherwise let us try to form a solution
287.759 -> and see how we can optimize it
292.56 -> okay so before trying to find an optimal
295.199 -> solution let us try to figure out how we
297.919 -> can approach this problem
299.919 -> a good developer will always try to come
301.919 -> up with a brute force solution
303.68 -> that is because it can guarantee you
306 -> that a solution to this problem exists
308.639 -> one way to approach this problem would
310.96 -> be to identify all the number of
313.12 -> distinct ways that you can climb
314.96 -> staircases
316.4 -> so let's say your value of n is one that
319.28 -> means you have only one staircase and
321.68 -> how can you climb it you can just take
323.759 -> one step and that would be it correct
326.639 -> you can climb the staircase in only one
329.44 -> way right
331.44 -> next let us say the value of n is two
334.88 -> this time you have two stairs right and
337.44 -> how can you climb it either you can take
339.6 -> one step at a time
341.36 -> or what you can do is you can directly
343.52 -> climb two stairs
345.36 -> so there are a total number of two waves
348.479 -> right
350.4 -> going forward when the value of n is
352.479 -> three that means you have three stairs
354.72 -> to climb
355.759 -> and how can you do that either you can
357.919 -> do one step at a time one one one
361.28 -> or you can do two steps and then one
363.52 -> step or you can do one step and then two
366.319 -> steps
367.68 -> so these are all the ways that you can
369.759 -> climb the stairs right
371.84 -> so when the value of n is three you can
374.4 -> climb the staircase in a total number of
376.72 -> three ways
378.96 -> similarly let's see what happens when
381.52 -> the value of n is 4
383.6 -> as soon as the value of n is 4 you can
386.16 -> climb these staircase in a lot of ways
388.479 -> right so what you can do is you can
390.72 -> either do one step at a time
393.039 -> or you can do two steps and then one
395.199 -> step and then one step or you can do one
397.84 -> step and then two steps and then one
399.759 -> step or you can do two steps and then
402.479 -> two steps again
403.84 -> so you see you have so many ways to
405.68 -> climb these right
407.12 -> there are a total of five ways
409.84 -> so when the value of n is four you can
412.56 -> climb the staircase in a total number of
414.72 -> five different ways
416.72 -> now this approach is correct and you
419.759 -> will ultimately be able to find a
421.599 -> solution no matter the value of n
424.08 -> if the value of n is 10 there will be so
426.479 -> many distinct ways that you can climb
428.08 -> the staircase
429.28 -> but at the same time finding those
431.759 -> combinations can get real hard
434.4 -> so you need to do something about it you
437.199 -> need to approach this problem in such a
439.199 -> way that you are not calculating these
441.84 -> results again and again
443.68 -> let us see how we can approach this
445.759 -> problem in a very smart and easy way
449.28 -> rather than directly giving you the
450.88 -> solution i want to take some time and
454 -> tell you how to approach these kind of
456.319 -> problems what should be a thought
458.24 -> process and how do you approach this
460.639 -> problem step by step
462.88 -> let us say i have this staircase in
464.96 -> front of me and this has a total number
467.44 -> of seven steps right
469.599 -> you are standing over here
471.44 -> and you want to reach the seventh most
473.68 -> step and you have to determine the total
475.84 -> number of ways
477.12 -> forget everything for a moment
479.199 -> let us say that you have to arrive at
481.36 -> step 7 right
483.28 -> and
484 -> what if the step 7 is your last step
487.68 -> how can you reach the last step
490.639 -> either you would be standing on step
492.24 -> number six and you will take one step
494.879 -> over here right
496.639 -> or what will you do
498.8 -> you would be standing on step number
500.56 -> five and your last step would be to take
503.919 -> two climbs and reach step seven right
508.4 -> so what i can say is that the total
511.36 -> number of ways to reach step seven
514 -> will be either you climb one stair from
516.88 -> step six
518.32 -> or you need to climb two stairs from
520.56 -> step five
521.839 -> right
522.64 -> think about it for a moment
524.56 -> now that you know that these are the
526.399 -> total number of ways you are either
528.399 -> climbing one stair from step six or you
530.48 -> are climbing two stairs from step five
533.2 -> so this problem can now translate into
536.56 -> the number of ways you're reaching step
538.64 -> 6
539.68 -> plus the number of ways you're reaching
541.92 -> step 5
543.2 -> so that simply means that the total
545.839 -> number of waves you can reach step seven
548.16 -> are the total number of waves you can
550.88 -> reach up to step six
552.8 -> plus the total number of waves that you
555.44 -> can reach up to step five
557.76 -> because after that you either need to
560.08 -> take one step to reach step seven or you
562.56 -> need to take two steps to reach step
564.48 -> seven right
566.88 -> just pause the video over here for a
568.88 -> while and let this sink in
571.839 -> based on this idea we can come up with a
574.56 -> very easy solution so just stop over
577.839 -> here and whenever you're ready let's go
582.48 -> okay so now try to gather all the
585.36 -> information that you have
587.12 -> what if you have only one stair and you
589.44 -> have to climb it how many ways can you
591.519 -> do that
592.48 -> you can climb one step at a time right
595.04 -> and that will tell you that you can
597.2 -> climb the staircase in a
599.04 -> one total number of ways right
602.16 -> move ahead
603.44 -> how can you climb two steps
606.32 -> the way to climb two steps would be
608.399 -> either you take one step and then one
610.32 -> step or you can climb two steps at a
612.72 -> time right
614.079 -> so you can climb
616.079 -> two stairs in a total number of two ways
619.2 -> correct
620.8 -> similarly
622 -> what happens if you have three stairs to
624.399 -> climb
625.519 -> based upon a previous idea that if you
627.839 -> have to reach step seven that would be
629.839 -> the total number of waves you can reach
632.079 -> step 6 plus the total number of ways you
634.959 -> can reach step 5.
636.88 -> i can derive a similar formula
639.44 -> the total number of waves to reach step
641.6 -> 3 will be equal to the total number of
644.8 -> ways you can reach step two plus the
647.12 -> total number of ways you can reach step
648.88 -> one
650.24 -> now what are the values that you know
652.8 -> you know the number of waves to reach
654.56 -> step two that is equal to two right
658.16 -> and you also know the total number of
660.56 -> waves you can reach step one
662.56 -> and that is equal to one
664.88 -> when you add up these two values
668 -> you will know the total number of ways
670.399 -> that you can reach step number three and
673.04 -> there are total of 3 ways right you know
676.079 -> 1 1 1
678.32 -> or 2 and then 1
680.88 -> or 1 and then 2
683.12 -> right
684.32 -> based upon this idea if you have to
686.24 -> reach step 4 that will be the number of
689.2 -> ways you can reach step two plus the
691.76 -> number of ways you can reach step three
694.48 -> so you get a general formula to solve
697.2 -> this question
698.32 -> and that will be the number of ways to
700.959 -> reach step n
702.399 -> is equal to the number of ways you can
704.399 -> reach step n plus 1
706.24 -> plus the number of ways you can reach
708.079 -> step n plus 2.
710 -> so this is dynamic programming
712.56 -> somehow in an array you are storing the
715.92 -> number of ways you can reach step one
717.76 -> then step two then step three then step
720.16 -> four
720.959 -> and if you want to calculate how to
722.8 -> reach step five that would be just the
725.12 -> addition of step four plus step three
728.32 -> and this is memoization
731.04 -> once all of this is clear to you writing
733.36 -> the code for this problem is very very
735.279 -> easy
736.24 -> just to sum everything up let us have a
738.24 -> look at it
740.72 -> on the left side of your screen you have
742.8 -> the actual code to implement the
744.32 -> solution
745.44 -> and on the right i have a sample test
747.92 -> case where the value of n is 8 that
751.04 -> means i will have a staircase that has a
753.2 -> total of n steps right
756.079 -> this n is passed in as an input
758.16 -> parameter to the function
760 -> oh and by the way the complete code and
762.8 -> its test cases are also available in my
765.04 -> github profile
766.399 -> you can find the link in the description
767.92 -> below
769.279 -> so what do you do next
771.2 -> you know that if you have only one step
773.92 -> you can only climb it in one way right
777.12 -> so you simply return one
779.2 -> if not you move ahead
781.12 -> now what you do is you create a array dp
785.12 -> that will store all the possible ways
787.519 -> that you can climb these stairs
789.839 -> and how do you initialize it you know
792.16 -> that you can climb one step in one way
794.72 -> and you can climb two steps in two ways
797.12 -> we have established this
799.2 -> so we will just populate this array
802.959 -> now moving ahead you can subsequently
805.36 -> calculate how can you reach step number
807.92 -> three
808.959 -> reaching step number three would be one
811.12 -> plus two
812.24 -> so you can reach step number three in a
814.56 -> total number of three ways right
818.48 -> this loop will continue all the way up
820.399 -> till n right so going forward you can
823.839 -> reach step number four in two plus three
826.88 -> that is 5 number of ways
829.12 -> then you can reach step number 5 in 3
832.72 -> plus 5 number of ways that is a total of
835.519 -> 8.
836.959 -> similarly going forward you can
838.959 -> calculate all these values 8 plus 5
841.44 -> would be 13 13 plus 8 would be 21
844.88 -> and then 21 plus 13 would be 34.
848 -> so you can climb eight staircases in a
851.6 -> total number of 34 distinct ways
854.56 -> and once you're out of this loop simply
856.639 -> return this answer
860.24 -> the time complexity of this solution is
862.399 -> order of n
863.68 -> that is because as the number of stairs
865.6 -> increase you need to keep on calculating
867.68 -> more and more values
869.199 -> and the space complexity of this
871.199 -> solution is also order of n
873.36 -> that is because you need to maintain
875.519 -> this dynamic programming array that will
878.32 -> store all the previous values
882.639 -> i hope i was able to simplify the
884.72 -> problem and its solution for you
887.04 -> as per my final thoughts take a moment
889.12 -> to realize how we came up with the
890.72 -> solution
891.92 -> we just use two building blocks right
894.88 -> we just determined that okay if you have
897.519 -> to climb one step what are the total
899.44 -> number of combinations and if you have
901.519 -> to climb two steps then what are the
903.519 -> total number of combinations
905.6 -> based on these two answers i was able to
908.72 -> determine the distinct number of ways to
911.76 -> climb the third stair and then the
913.44 -> fourth and the fifth right
915.519 -> it was so easy
917.279 -> you just need to focus on the logic when
920.399 -> you're solving problems on dynamic
922.24 -> programming
923.36 -> don't get scared by big words like
925.279 -> memoization and oh my god dp what do you
928.24 -> do about it
929.36 -> never be scared
930.8 -> just follow step by step what the
933.44 -> problem statement is trying to say
935.519 -> and solve a small portion
938.16 -> that small portion can expand into the
940.56 -> entire problem itself
942.56 -> you see for yourself when you saw the
944.56 -> code how small the solution was
947.519 -> this is the beauty of dynamic
948.959 -> programming
950.16 -> what problems did you face when you were
951.92 -> solving this problem
953.36 -> can you find some other efficient
955.04 -> methods tell me everything in the
956.959 -> comment section below and i would love
958.48 -> to discuss all of them with you
960.24 -> you would be also glad to know that a
962.24 -> text based explanation to this content
964.079 -> is available on the website
965.44 -> studyalgorithms.com
967.199 -> a pretty handy website for your
968.72 -> programming needs you can find the link
970.639 -> in the description below
972.24 -> as a reminder if you found this video
974.16 -> helpful please do consider subscribing
976 -> to my channel and share this video with
977.6 -> your friends this motivates me to make
979.839 -> more and more such videos where i can
981.519 -> simplify programming for you
983.6 -> also let me know what problem do you
985.199 -> want me to solve next or rather what do
987.36 -> you want to learn next i'll be glad to
989.6 -> help you out
990.72 -> until then see ya
Source: https://www.youtube.com/watch?v=UUaMrNOvSqg