The Recursive Staircase - Top Down & Bottom Up Dynamic Programming ("Climbing Stairs" on LeetCode)

Поделиться
HTML-код
  • Опубликовано: 4 дек 2024

Комментарии • 294

  • @BackToBackSWE
    @BackToBackSWE  5 лет назад +21

    Table of Contents:
    A Short Message From Our Sponsors 0:00 - 1:15
    The Problem Introduction 1:15 - 3:25
    Top-Down Approach (Without Memoization) 3:25 - 10:56
    Duplication of Work: Why We Memoize 10:56 - 12:12
    Pruning The Work Tree 12:12 - 14:06
    The Bottom-Up Approach 14:06 - 17:18
    Time & Space Complexities 17:18 - 18:40
    Subscribe & Be My Friend 18:40 - 19:12
    The code for this problem is in the description. Fully commented for understanding with both the top down and bottom approaches.

  • @queensfinezt
    @queensfinezt 5 лет назад +55

    2:38 golden "Tushar take it away"

  • @ayodejiakinola7343
    @ayodejiakinola7343 4 года назад +30

    Finally, an explanation that makes sense beyond intuition. I really appreciate this

  • @TheChromeLegend
    @TheChromeLegend 5 лет назад +46

    I just discovered your channel like a few days ago but these are so good. Such a clear explanation and walkthrough. You're killing it, dude!

    • @TheChromeLegend
      @TheChromeLegend 5 лет назад +1

      Quick question lol. You mention that you've been through EPI several times, did you follow the schedule in the beginning of the book? Or did you solve every problem in the book? How long did your first walkthrough take? I'm asking because I'm currently job hunting as a new grad. Thanks :)

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      Thanks!

  • @_hello_5346
    @_hello_5346 2 года назад +2

    This is the most clear explanation of this problem I have seen so far. In most other videos they take the bottom-up approach when they explain it, and it becomes confusing real quick. Drawing the recursion tree top-down was really helpful.

    • @BackToBackSWE
      @BackToBackSWE  2 года назад

      Thanks! why dont you subscribe to our exclusive DSA course and avail 30% discount for some great content b2bswe.co/3HhvIlV

  • @narihanellaithy7726
    @narihanellaithy7726 5 лет назад +15

    The recursion tree at the beginning is spot on! thank you!

  • @mfkman
    @mfkman 4 года назад +4

    I totally agree with you that all of these problems have nothing to do with the day to day problems that software developers work on. Having been a software developer for 15+ years, mainly backend C++ code that runs on hundreds of servers, I honestly find asking dynamic programming questions (and similar) in interviews ridiculous. But as someone interested in maybe changing jobs, you have to know this stuff as all the big companies for some reason ask you these questions, not sure why. I think your and Tushar Roy's channel as well as actual practice on Leetcode are the best resources out there to practice for the larger companies that ask these types of problems. Thanks for all the work you are putting into this!

  • @qwarlockz8017
    @qwarlockz8017 3 года назад +1

    I always come back to you and Tushar for clear explanations that make sense and are accessible

  • @seanchon
    @seanchon 5 лет назад +7

    This is such a great explanation. I am a working software engineer, but really out of practice with some fundamentals. And I hardly think of problems of this nature during my day-to-day. This explanation made this problem look so much easier than my original wtf moment. Thank you!

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад +2

      Sean. This is Ben. It is an honor to have taught you this problem. The reason I do this is because of people like you
      I know that there are people in your position and my aim is to make your life a little easier because these problems suck. I hope you keep growing and keep succeeding.

  • @shaunvaughn3323
    @shaunvaughn3323 5 лет назад +7

    Thanks for this video. Finally someone who can clearly explain top down vs bottom up DP. You are a great teacher man. Keep it up. You just saved me hours and hours of headache.

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      Thanks.....and.................................hi

  • @danielkashkett7040
    @danielkashkett7040 3 года назад

    watched at least 4 videos about this problem, this is the first one that actually makes sense.

  • @sifatmoonjerin2479
    @sifatmoonjerin2479 4 года назад +2

    I don't know why but as I am preparing for my interview, I keep coming back to this channel every now and then. Great work!

  • @Gary1q2
    @Gary1q2 4 года назад +1

    I feel out of RUclips you are the best explainer of dynamic programming. You break everything down into the simplest of things and keep it paced really well to make sure everybody understands.....Thanks for the video!!! U are a fantastic teacher dude

    • @BackToBackSWE
      @BackToBackSWE  4 года назад +1

      Yes - because I understand it really well and can articulate it in a way a general person can understand it.

  • @SatyadeepRoat
    @SatyadeepRoat 4 года назад +2

    I got a similar question in one of my interview to return the total ways.
    Eg: totalWays(n, steps); eg: totalWays(3, [1, 2]) should return [[1, 1, 1], [2, 1], [1, 2]]
    . I started solving the question using dynamic programming . But in the middle I thought that i need to find all the ways. And all I could hear in my ears was someone shouting "whenever we have to find all possibilities or generate all, then we are dealing with a backtracking problem". And immediately jumped on the pattern of backtracking and solved the question the same way you taught in the video of permutation of string. Aced the interview like a boss with no mistakes

  • @jujubi123-h7k
    @jujubi123-h7k 3 месяца назад

    Really love the logical flow of the teaching, it helped me! Thank you!

  • @shritishaw7510
    @shritishaw7510 3 года назад

    That branch cutting is very satisfying. This is my first video on this problem and is also the last video for the same. Thanks a lot for the amazing explanation. Cheers.

  • @josecunha6974
    @josecunha6974 3 года назад

    Like many working programmers, became one from one the job training not so much study and theory. But the theory and logic fascinate me now. Was able to write an algorithm C# that worked, once someone told me about the relationship to the Fibonacci sequence, but now I know WHY it relates to Fibonacci. Live and learn, love it, very intuitive, you're the man.

  • @lamsaitat
    @lamsaitat 5 лет назад +1

    Great work! This is the only teaching material by far that explains the base case properly after reading hundreds of those that simply says "declaring F(0) = 1 is easier"

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      Thank you. I'm honored that you even watched this.

    • @lamsaitat
      @lamsaitat 5 лет назад +1

      @@BackToBackSWE 5 months later still the only tutorial that makes sense top-down or bottom-up :'D

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      @@lamsaitat haha, yoyo

    • @wtcxdm
      @wtcxdm 2 года назад +1

      @@BackToBackSWE Hi, I am still slightly confused about f(0) = 1... how does doing nothing count as 1? Can I interpret there are three moves you can make like 0, 1 and 2 steps? Except 0 step won't get you anywhere forward

  • @davesmith5043
    @davesmith5043 2 года назад

    This man is amazing wow, I couldn't for the life of me understand this problem before and now its crystal clear! I was blind and now I see!

  • @abcdeereijgfhd3215
    @abcdeereijgfhd3215 3 года назад +1

    Great! You are one of the best teachers on youtube.

  • @yashnanda4864
    @yashnanda4864 3 года назад

    I notice myself getting so much better after watching many of your videos. Now in half of your videos I figure it out in a moment and say to myself "well that was kinda obvious"

  • @TheBarbaraMouse
    @TheBarbaraMouse 4 года назад +1

    I found it hard to start solving DP questions, but since I found out this channel it's much more intuitive! Wherever I've read about where to start and how to think when solving these kind of problems, nobody could explain thinking process better than you. Great job :)

  • @kirancoding1576
    @kirancoding1576 5 лет назад +2

    As I always say 'the best explanation' I request you to make more and more videos like this .I will make sure all of my friends watch videos of your channel

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      Nice! I will be releasing a course in 1-2 months, stay tuned

  • @venkateshn9884
    @venkateshn9884 2 года назад +1

    This one is the best explanation for this problem I have ever seen... 🔥🔥🔥

  • @SK-lu7ci
    @SK-lu7ci 4 года назад +1

    Awesome, Nothing beats your "falling egg , find pivotal floor" problem explanation...

  • @talesfromthemidwest
    @talesfromthemidwest 5 лет назад +3

    Finally, an explanation that makes sense.

  • @marceldegas
    @marceldegas 4 года назад +1

    You are an excellent teacher man! I taught high school for 6 years and game recognize game, you have a talent :D

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

      Hahahahaha thanks

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

      I love the game!!!!

    • @marceldegas
      @marceldegas 4 года назад

      @@BackToBackSWE haha, play on playaaaa :D Can I ask, how did you get started teaching Algorithms? I went from Biology teacher to SWE a couple of years ago, but Im trying to find a way to get back into teaching!

  • @arxci9402
    @arxci9402 4 года назад +3

    This video was honestly so helpful. Solved the problem first try.

  • @gimmeerkin2131
    @gimmeerkin2131 3 года назад +1

    The best explanations(for different tasks) I have found 👏🏻

  • @Finn-jp6pn
    @Finn-jp6pn 5 лет назад +10

    I LOVE YOU ❤️! I'll be your patreon when I get a job. Thanks!

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад +6

      No worries, just get the job haha. And love you too.

  • @matthewbuchholz7091
    @matthewbuchholz7091 4 года назад +5

    "We're gunna keep expressing *shakas emphatically* our decisions" xD love it

  • @ginasomara267
    @ginasomara267 2 года назад

    BEST video I have seen on this. TY

  • @Anonymus1232-x
    @Anonymus1232-x 3 года назад

    Just wanted to say a quick thank you! Had a Data structure and algorithm class this semester and you videos helped me so much understanding how you need to think when solving problems

  • @cooperwsu7206
    @cooperwsu7206 4 года назад +2

    alright I am here to say WOW, that tree helped me out so much... like seriously amazing. I never have thought of it like that before

  • @smithcodes1243
    @smithcodes1243 3 года назад

    This is by far the best explanation! Thanks buddy!

  • @killeraloo3247
    @killeraloo3247 Год назад

    Thank you so much, you always make difficult looking problems, easy. 🧡 from India.

  • @DadBodSwagGod
    @DadBodSwagGod 5 лет назад +1

    I know this wasn’t your intention because how could it have been, but I just had a revelation about myself and why I’ve been struggling with interview questions thanks to you

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      lol nice

    • @blasttrash
      @blasttrash 5 лет назад +1

      revelation? what was that? I am curious...I might have the same revelation too if you let us know. :D

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      @@blasttrash yo

    • @blasttrash
      @blasttrash 5 лет назад +1

      @@BackToBackSWE yo, whats up. Hope you have a nice weekend. :D

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      @@blasttrash The weekend just happened

  • @shubhamuniyal2417
    @shubhamuniyal2417 5 лет назад +3

    Love how u break things down into subproblems 😅 great work dude

  • @2tce
    @2tce 4 года назад +1

    Watched a couple of your videos. Super insightful and well taught! Many thanks.

  • @amithbk12man
    @amithbk12man 4 года назад +1

    I really liked the way you explain. Thanks!

  • @krishnanigalye1173
    @krishnanigalye1173 3 года назад

    Awesome explanation dude. I was trying to avoid this topic like forever. This is super cool. Thanks a ton!

  • @maximedero4270
    @maximedero4270 5 лет назад +1

    Thank you so much, I did not catch before what was the purpose of memorization. You have explained it very well !!

  • @tejasvigupta07
    @tejasvigupta07 4 года назад +1

    Such a great explanation.Instant subscribe.

  • @rchukkapalli1
    @rchukkapalli1 4 года назад +1

    Subscribing after watching the steps problem. Thank you for your efforts. Please keep educating us.

  • @wilsonjiang8849
    @wilsonjiang8849 5 лет назад +1

    Amazing video, found it in the Leetcode discussions section, subbed !

  • @biswajitnayaak
    @biswajitnayaak 3 года назад

    i wish u were my teacher when i studied software engineering 14 years back

  • @kosamganjoo5694
    @kosamganjoo5694 4 года назад +1

    why this video has not million hits? he is too good

  • @Arnott_me
    @Arnott_me Год назад

    Thanks a lot, finally understand how it works!!

  • @MacaroonL
    @MacaroonL 4 года назад +3

    Thank you!! This video was really helpful!

  • @rajatjain7680
    @rajatjain7680 4 года назад +1

    you made it so simple to understand for me. Thank you

  • @kuxnal
    @kuxnal 2 года назад

    this man is awesome. thank you so much for this!

  • @markfesenk0
    @markfesenk0 4 года назад +1

    Two things:
    1. the time complexity is actually O(mn) where m is the number of possible steps sizes (in this case 1,2)
    2. the O(n) time complexity sounds good but you should have mentioned that it is actually exponential to the input value (of 6 in the example)
    Great videos man

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

      I don't remember this video much so can't validate 1, and ok for 2. And ok

    • @vinayakmishra9519
      @vinayakmishra9519 4 года назад

      Yeah both the points are true.

  • @МарияСкрягина-щ9з
    @МарияСкрягина-щ9з 5 лет назад +1

    Awesome explanation, I am not afraid of DP anymore :)

  • @luisasanchez9267
    @luisasanchez9267 3 года назад

    Amazing explanation and intro to these sort of algorithms. Congrats!! :D

  • @SoledadDelSol
    @SoledadDelSol 3 года назад

    Great explanation for this problem!

  • @PomboKad
    @PomboKad 4 года назад +1

    You just got a new subscriber. Thank you!

  • @kalusharma2201
    @kalusharma2201 5 лет назад +4

    Holy shit dude, you gave *the best* explanation! Thanks a lot!!

  • @vineethm6930
    @vineethm6930 4 года назад

    Thanks a lot for strengthening my concepts.

  • @mallikarjunpidaparthi
    @mallikarjunpidaparthi 4 года назад +1

    Thank you sir. With the help of your explanation I was able to code the problem in both the ways I.e., top down and bottom up. I have a question. What is the difference between Memorization and Dynamic Programming as they both are used to save us from computing the same sub problem again. Thank you sir...

  • @bhargavsai2449
    @bhargavsai2449 4 года назад +1

    superb!!! superb!!great work

  • @shiladryadak1541
    @shiladryadak1541 4 года назад +1

    oh finally I got it!! Thanks a lot!!

  • @kausachan4167
    @kausachan4167 4 года назад +2

    converting to code in python(works only for n=6):
    n=6
    list1=[1,1,1,1,1,1,1]
    for i in range(2,n+1):
    list1[i]=list1[i-2]+list1[i-1]
    print(list1[n])
    JUST WORK IT OUT FOR DIFFERENT VALUES BY ALTERING THE 'N' VALUE AND LIST SIZE*

  • @sapunovnik
    @sapunovnik 5 лет назад +1

    Great explanation! Thank you very much!

  • @akankshasharma148
    @akankshasharma148 3 года назад

    Great explanation 🙏🙏🌼

  • @vandanpatel3395
    @vandanpatel3395 4 года назад +1

    This was excellent, you are a rockstar! Just one follow up question: Can you give us an example where one approach is significantly better than the other one?

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

      thanks and I dont remember this video much tbh

    • @vandanpatel3395
      @vandanpatel3395 4 года назад

      @@BackToBackSWE No problem, I completely understand. Thanks for your response. Please stay safe!

  • @Allen-tu9eu
    @Allen-tu9eu 3 года назад

    what a nice intro for dp

  • @woodylucas
    @woodylucas 4 года назад +1

    White boarding goes a long way! as soon as you broke down working from the top and subtracting 1 step, subtracting 2 steps, and the total of that sum gives you how many steps you need to take--it CLICKED! Thanks

  • @yaminchoudhury8732
    @yaminchoudhury8732 4 года назад +1

    your a cool guy man thank you for everything

  • @SolamanRaji
    @SolamanRaji 3 года назад

    Great explanation man :)

  • @mybrightmeteor
    @mybrightmeteor 5 лет назад +3

    Thank you very much, your goal deserves nothing but admiration! Out of those many videos on the topic out there, I find yours absolutely the best!
    Can you please help me understand something:
    1. This problems at a first glance is very similar to the coin change problem. With the key difference being that with coins order doesn't matter (hence we have less combinations), while with the stair order matters as the same set of steps could yield different ways of climbing (permutations). Understanding that I'm still not catching where exactly this difference is accounted for in those two algorithms. Where should I look?
    2. I missed the intuition behind the "+" operation (n = (n-1) + (n-2)). When you do add those, it's easy to see the Fibonacci sequence but I do not understand why we should use the '+' there in the first place. In other words I seem to have missed the intuition on why the number of ways to climb N steps equals the number of ways to climb n-1 steps plus n-2 steps.
    I'd appreciate your help with those) .

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад +2

      1.) Consider that what we are really saying is...the answer to dp[i] is the cumulation of all the possible ways if the LAST step we take is 1 step or 2 steps. It is very similar to the coin change problem, just the formatting changes. The fundamental reasoning is the same. So consider that...from any point...our last step uniquely identifies the path to where we stand...which is 'i' steps left to consume. This is why order does matter. That last step makes any path up to our current destination unique. That is the distinction.
      2.) The intuition is the "last step" idea. The unique "footprint" to a path is the last step taken to where we are. So to get to n we have 2 unique choices that differentiate our progress up to that point....1 step and 2 step... as the final step. This is the intuition...and consider that we drill to base cases where we KNOW the answer. (and these base cases are like a net we can make as wide as possible, or as shallow as possible). When I add dp[i -1] and dp[i - 2] I am saying that the answer to the subproblem dp[i] IS THE SAME as the sum of ALL the ways if my last step is a 1 step or a 2 step.
      I'm kinda mentally tired from schoolwork that I got behind on so the above may not be enough for you to really understand this, if you have any questions continue asking, I will answer (and hopefully be less mentally foggy later).

    • @sandeeps7625
      @sandeeps7625 5 лет назад

      Back To Back SWE this comment too helped a lot , thanks

  • @jyl4990
    @jyl4990 5 лет назад +1

    Great video! you just got another sub! Keep it going!

  • @ShreyanGoswami
    @ShreyanGoswami 4 года назад +1

    One of the interesting things to note here is that in case if you only have the option of taking 1 or two steps back it boils down to finding the nth Fibonacci number because the current value is the sum of the previous two with the base case and the number of ways to take the first step being 1. So in case you want to impress your friends you can say hey if you climb these stairs by taking either one step or two, the number of ways to do so is the nth Fibonacci number where n is the number of steps.

  • @BaishaliGhosh13
    @BaishaliGhosh13 5 лет назад +1

    This is a great explanation. I also want to understand how to handle the same question with some constraints thrown in Could you please help me understand how to proceed with a variant of this problem?
    The question is as follows: I need to reach n stairs by taking 1 step or 2 step or 3 steps. However, I can only take 3 steps at most b times. What are the total number of ways I can reach the n steps?

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад +2

      Sounds like that could be solved by restricting the recursion & keeping state on the number of 3's used so far

  • @sinat101
    @sinat101 3 года назад

    This (and many videos similar to it) establish the fact that knowing how many unique ways to N stairs is simply adding the unique ways to N-1 to the unique ways to N-2. My question and what I'm confused about is, how do we already know this? Is this is a common/expected known statistic or probability thing?

  • @sandeeps7625
    @sandeeps7625 5 лет назад +1

    OMG , this is awesome , thanks a lot!!!! , SUBSCRIBED

  • @4sky
    @4sky 5 лет назад +3

    For me it wasn't clear why the solution to 6 would be the solution to 4 + 5.
    But I finally got it and just putting the logic here if others don't get it.
    You need to add 2 steps to all the solutions in 4 to get 6 steps. And you need to add 1 step to all the solutions in 5 to get 6 steps. The combination of those solutions are the answer to 6.

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      oops

    • @mengruli4103
      @mengruli4103 5 лет назад

      if DP is hard to understand at the first place, you can solve it by recursion. The recursive function will return iff it reaches the leaves of the tree, and the parent of the recursion tree will see the # of valid leaves. ff you do 4+5, after finishing the recursion, you will get # of all child nodes traversed not only the leaves

  • @sriramkasu7511
    @sriramkasu7511 4 года назад +1

    bro you are too good

  • @punstress
    @punstress 4 года назад +2

    4:45 It always seems to me that the sum of the steps to get to 4 and the steps to get to 5 is either not enough (depending on how I look at it), because I haven't gotten to 6, or too much, because if I add 4 and 5 I get 9. I still have to think about it. I mean, from the root, you took 1 or 2 steps. So why aren't you adding those steps back in?
    The tree helped a lot. I understand the dp but I have trouble understanding the logic. I'm working on a problem where you can take 1, 2, or 3 steps, and whenever I figure it myself, I'm off by one.
    Having code would be incrementally better but then you have to decide on a language and you won't please everybody. But your work is far above geeksforgeeks. I don't know how they got on top of google (wouldn't be surprised if they worked there and know the algorithm). I always search with their name excluded.
    update: It finally made sense. I drew out the first steps (3 for my problem. [1] | [1,1],[2] | [1,1,1],[1,2],[2,1],[3] and it was easy to see that I would add 3, 2, or 1 steps to make 4. And then, it's induction. I used a list and passed all my tests. Yay!

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

      Google ranked them overtime and they have thousands of trafficked pages. Content on the internet doesn't have to be good to succeed (though it helps). It just has to be "there" for a long time.

  • @arsyaswanth5
    @arsyaswanth5 5 лет назад +1

    Dude you're awesome!!!

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      no you are awesome

    • @arsyaswanth5
      @arsyaswanth5 5 лет назад

      @@BackToBackSWE dude i was just seeing your knapsack video and your comment popped up lol!!!

  • @pranavparihar4744
    @pranavparihar4744 4 года назад

    Thanku so much for the explanation :)

  • @airysm
    @airysm 5 лет назад +3

    Hey Ben, when do you recommend top down vs bottom up? To me bottom up always seems like the most easy to implement

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад +4

      Yeah, what you just said is true. I agree with that. I just have a knack for top down, not sure why. It is just cool.

  • @JG-zu6nq
    @JG-zu6nq 5 лет назад +2

    Good stuff bro.

  • @mikasaackerman2694
    @mikasaackerman2694 4 года назад

    8:54 Loved the way you explained recursion lol

  • @InnovatetoLife
    @InnovatetoLife 5 лет назад +1

    Dude ❣️ best explanation

  • @billy-cg1qq
    @billy-cg1qq 2 года назад

    Hello, thanks for the video, it was very informative. But how did you calculate the complexity being O(1.62^n)? How did you get O(2^n)?

  • @shoco2
    @shoco2 3 года назад

    Great explanation!

  • @Taeyang311
    @Taeyang311 5 лет назад +1

    Thanks for the video!

  • @AbhishekChauhan-wt1hb
    @AbhishekChauhan-wt1hb 5 лет назад +1

    Quality content ..Thankyou so much

  • @free-palestine000
    @free-palestine000 3 года назад

    I know this isn't really the point of the vid, but how did you calculate the exact bound (theta) @11:56?

  • @techsavvy1457
    @techsavvy1457 5 лет назад +8

    Follow-up: Return the steps

  • @helloiam2mas
    @helloiam2mas 4 года назад +1

    This may sound dumb, but from a conceptual standpoint, why is the number of ways to reach a certain stair the sum of the ways you can reach the current stair -1 and -2 (assuming only 1 and 2 steps)? Like shouldnt we add a +1 because we are technically adding a new way to get to up to the current stair?

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

      No ur gud - there is no dumb. If you are attempting critical thinking and trying hard there is only improvement.
      And I get your angle, but the idea is to consider everything behind even step -1 and step -2 because those have dynamic answers as well. You are thinking along the right lines.

    • @helloiam2mas
      @helloiam2mas 4 года назад +1

      @@BackToBackSWE But what about even at lets say, step 3. Why is the number of ways to get to step 3, the number of ways you can go up step 2 + number of ways you can go up step 1? Like from a conceptual standpoint, why does that make sense? Like why dont we add number of ways to go up step 1 + number of ways to go up step 2 + 2 (because either 1 step or 2 steps)?

  • @刘恒-o7k
    @刘恒-o7k 4 года назад

    Awesome, man!!!

  • @arunadang2130
    @arunadang2130 4 года назад +1

    Good one

  • @theredorm1961
    @theredorm1961 5 лет назад +1

    Good luck, you get really cool

  • @jithinMumbai
    @jithinMumbai 5 лет назад +1

    Can you explain in Bottom up approach, .i.e Tabulation, the advantage of storing values in Tables. Is it because any future execution of the function, will save time by not needing to calculate from the base cases.
    For example, Once F(6) = 13 is calculated, For F(8) I just need to calculate F(7), instead of calculating again from F[0] to F[7] ??

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      "Is it because any future execution of the function, will save time by not needing to calculate from the base cases." Yes. The code won't solve paths already solved, thus saving time.

  • @sophiehall38
    @sophiehall38 5 лет назад +1

    All right, I have watched many of your videos, and I always have one same question. I need to ask you now...so, can you tell me what exactly your filming camera is? I really like the shot! Thx again!

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

      Canon Rebel T3i

    • @sophiehall38
      @sophiehall38 5 лет назад

      @@BackToBackSWE Thanks for your reply! Have a nice day!

  • @sahilanand30
    @sahilanand30 3 года назад

    great explanation :)

  • @pudisasikar7996
    @pudisasikar7996 4 года назад +1

    Great video... But i didn't find any link in description for code.. Is it missed

    • @BackToBackSWE
      @BackToBackSWE  4 года назад +1

      Hi - the repository is deprecated, we only maintain backtobackswe.com now.

    • @pudisasikar7996
      @pudisasikar7996 4 года назад

      @@BackToBackSWE wow.. Thxs 4 quick reply.. I'm just going through recursion videos... Your bottom approach & top down approach is just awesome.. Very easy to understand.. Thank you very much

  • @wl7497
    @wl7497 5 лет назад +1

    Great tutorial! One quick question, why we make our memo array size of n + 1? is it because we store one more 0 for n < 0?

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад +2

      No, it just helps with indexing. Our answer ends up at index n instead of n - 1. Adding the 0 at the front pushes all elements to the right by 1. + 1 to each index.

  • @dinner4chiahao
    @dinner4chiahao 2 года назад

    Great video! Thanks!

    • @BackToBackSWE
      @BackToBackSWE  2 года назад

      Thank you, glad you liked it 😀
      Do check out backtobackswe.com/platform/content
      and please recommend us to your family and friends 😀