Climbing Stairs - Dynamic Programming - Leetcode 70 - Python

แชร์
ฝัง
  • เผยแพร่เมื่อ 3 ก.พ. 2025

ความคิดเห็น • 663

  • @NeetCode
    @NeetCode  3 ปีที่แล้ว +50

    🚀 neetcode.io/ - A better way to prepare for Coding Interviews

    • @algorithmo134
      @algorithmo134 3 ปีที่แล้ว +1

      @NeetCode can you do binary tree cameras?

    • @alexandermilligan8265
      @alexandermilligan8265 2 ปีที่แล้ว +1

      Actually I think the brute force decision tree solution has a time complexity of Phi in the power of n, and not 2 in the power of n, seeing as it grows similarly to Fibonacci series.
      Great video by the way!

    • @monstereugene
      @monstereugene 2 ปีที่แล้ว

      why have a temp variable when you could write:
      two = one
      one = one + two ?
      Edit: Oh it's because it would change the one plus two line duh

    • @NitrakGaming
      @NitrakGaming 2 ปีที่แล้ว +1

      Instead of using a temp-variable you can make use of Python3s tuples (as you already are when you create the variables).
      one, two = 1,1
      for i in range(n-1):
      one, two = one + two, one
      return one
      Behind the scenes it is effectively the same as using a temp variable, but without the ugliness of one! :)

    • @praffulkumarsingh1346
      @praffulkumarsingh1346 6 หลายเดือนก่อน

      Using base condition, when at 5(n=5 problem), why there is 1 way to reach 5, as you already stand there, why Not Zero(0) ?? Can anyone tell ?

  • @max3446
    @max3446 3 ปีที่แล้ว +770

    this is probably the hardest 'easy' tag question I've come across

    • @warguy6474
      @warguy6474 ปีที่แล้ว +46

      if I didnt recognize the fibbonacci i would have been screwed lol

    • @freshmarcent2741
      @freshmarcent2741 ปีที่แล้ว

      literally, every single solution I saw besides fibbonacci I just do not understand lol@@warguy6474

    • @trh786fed
      @trh786fed ปีที่แล้ว +5

      @@warguy6474i didn't know the fibbonacci before this video

    • @warguy6474
      @warguy6474 ปีที่แล้ว +12

      @@trh786fed I think if you take an intro computer science course in highschool or college they usually address it once but that's pretty much it

    • @mohd.tabishkhan4868
      @mohd.tabishkhan4868 8 หลายเดือนก่อน +1

      Wait until you checkout 1002 : Find Common Characters

  • @CSBAjay
    @CSBAjay 2 ปีที่แล้ว +157

    Thank u very much!!! Because of your tutorials, I got interest and thinking visually for solving DSA problems.. Now I have a job in MNC too..

    • @demonslayer4607
      @demonslayer4607 ปีที่แล้ว +6

      how do u visualise dsa ??

    • @shawcking2472
      @shawcking2472 ปีที่แล้ว +41

      ​@@demonslayer4607by closing his eyes.

    • @prathameshjadhav3041
      @prathameshjadhav3041 ปีที่แล้ว +2

      @@demonslayer4607decision tree ?

    • @sanketkadlag
      @sanketkadlag 6 หลายเดือนก่อน

      can we connect?

    • @ehm-wg8pd
      @ehm-wg8pd 2 หลายเดือนก่อน

      @@demonslayer4607 i suppose, this entire channel visualizing DSA

  • @Huytn-12
    @Huytn-12 3 ปีที่แล้ว +704

    your videos should be in Leetcode's editorial solutions. Clear, concise, and so easy to understand.

    • @abaibekenov6107
      @abaibekenov6107 3 ปีที่แล้ว +13

      This! Please! Once I've gone through several channels to understand dynamic programming and haven't done it ever since I found your channel. There's simply no need anymore, as not a single channel imo can beat @NeetCode 's way of explaining things! This guy is just phenomenal!

    • @jjayguy23
      @jjayguy23 ปีที่แล้ว

      He's a genius! His videos are such a blessing!

    • @kirillzlobin7135
      @kirillzlobin7135 ปีที่แล้ว

      Definitely. Leetcode should pay him

    • @jst8922
      @jst8922 ปีที่แล้ว

      This guy is too very good in explanations www.youtube.com/@nikoo28 , only difference is he doesn't use python but Java instead.
      for current problem
      th-cam.com/video/UUaMrNOvSqg/w-d-xo.html

  • @wrestlingscience
    @wrestlingscience 3 ปีที่แล้ว +212

    17:40
    " ah Yes.. makes sense so far"
    17:50
    "WAIT ITS OVER?!"

  • @MrFrawsty
    @MrFrawsty 2 ปีที่แล้ว +37

    Bro I don't know how you're so good at simplifying things, but it's incredible. I've watched so many videos on dynamic programming and not one of them has made as much sense as this. I sincerely thank you for all of these videos.

  • @floroz87
    @floroz87 2 ปีที่แล้ว +40

    I am preparing for an interview and your videos are simply the best thing I found on the internet.
    Thank you for your hard work it's helping hundreds of us!

  • @kleadfusha8338
    @kleadfusha8338 3 ปีที่แล้ว +84

    The most underrated channel on TH-cam!!

  • @techmemes3266
    @techmemes3266 3 ปีที่แล้ว +406

    12:08
    Why is the value for the base case 1? I would have thought it's 0 because if we start at 5, we only have the choice to take 1 step or 2 steps, both of which would lead to out of bounds

    • @vigneshv5092
      @vigneshv5092 3 ปีที่แล้ว +49

      I too have same question, it should be zero

    • @muthuksubramanian4143
      @muthuksubramanian4143 3 ปีที่แล้ว +16

      Same question, Any leads ? Thanks

    • @Deschuttes
      @Deschuttes 3 ปีที่แล้ว +27

      Agreed. That doesn't make sense.

    • @Tuyenrc
      @Tuyenrc 3 ปีที่แล้ว +9

      same question here, has anyone found out?

    • @DeepSheth1
      @DeepSheth1 3 ปีที่แล้ว +97

      It should be zero. This problem has 3 bases cases.
      1) dp[n-1] ➜ 0 steps
      2) dp[n-2] ➜ 1 step
      3) dp[n-3] ➜ 2 steps
      Now, we can determine the remaining sub-problems. The drawn out approach is explained bottom-up, but the coded solution isn't bottom-up. Here's my bottom-up solution in javascript
      let currentStep = 0;
      let previousStep = 1;
      let totalSteps;
      // start at the end and move to index 0
      for (let i = n-1; i >= 0; i--) {
      totalSteps = currentStep + previousStep;
      currentStep = previousStep;
      previousStep = totalSteps;
      }
      return totalSteps;

  • @xynergy645
    @xynergy645 3 ปีที่แล้ว +121

    OMG, thank you so much for the clear explanation. I've been struggling to understand the recursion method and why the complexity of Memoization is O(n) for a while. Your decision tree explanation is fantastic and I can finally have a good sleep tonight.

  • @dazai9015
    @dazai9015 3 ปีที่แล้ว +27

    Your explanations are so good, I'm so grateful that I get to watch your videos.

  • @nitiketshinde1458
    @nitiketshinde1458 3 ปีที่แล้ว +18

    Your explanations are really helpful! and efficient I don't know why this channel or video is very less subscribers/views , most underrated. YOU DESERVE BETTER ! keep it up

  • @jcoder8965
    @jcoder8965 2 ปีที่แล้ว +3

    Beautifully explained. You really took the time to first establish what the problem was asking. I really appreciate you breaking down this problem conceptually and then proceeding to highlight how and why dynamic programming was the way to approach this problem through the use of DFS, recursion and memoization. Instead of just providing the 5 line solution after a few minutes of going through this problem, you took the time to provide an in-depth explanation and help cement the PROCESS of arriving at solution in my mind. So glad I subscribed to your channel and thank you very much!

  • @dsptchr
    @dsptchr ปีที่แล้ว +2

    Literally the only person that actually explains this solution fully. It's unbelievable how badly others explain even the task.

  • @sankalp1391
    @sankalp1391 3 ปีที่แล้ว +24

    Great Explanation!
    For others like me, who feel that the number of steps at the 'nth' step (last step) should be 0, the below solution is adapted accordingly:
    # computing the base case, when we are on the penultimate (n-1) step, or the one before the penultimate (n-2) step
    penultimate_step, one_before_penultimate = 1, 2
    if n == 1: return penultimate_step
    if n == 2: return one_before_penultimate
    for i in range(n-2):
    one_before_penultimate, penultimate_step = penultimate_step + one_before_penultimate, one_before_penultimate
    return one_before_penultimate

    • @khaja-vali
      @khaja-vali หลายเดือนก่อน

      Thanks, took bit more time to understand but helps a lot.

  • @f3nrir_
    @f3nrir_ 3 ปีที่แล้ว +86

    if you consider the base cases of dp[n] = 0, dp[n-1] = 1, dp[n-2] = 2, you can complete the rest using Neet's solution and in that case there is no confusion regarding why dp[n] = 1.

    • @TaiChiSWAG
      @TaiChiSWAG 2 ปีที่แล้ว +9

      I was having the same doubt, Thanks

    • @darioarielgonzalezleegstra1741
      @darioarielgonzalezleegstra1741 ปีที่แล้ว +11

      this makes much more sense. I still don't get why do we say there is "1" step from dp[n] if we are already in the last step and there are no steps to do.

    • @sapientia230
      @sapientia230 ปีที่แล้ว +5

      @@darioarielgonzalezleegstra1741 because your current position is also the target position (top position) and there is only one way to go there by doing absolutely nothing

    • @PrafulPrasad
      @PrafulPrasad 9 หลายเดือนก่อน +3

      @@sapientia230 but then it means 0 ways, because it doesn't make any sense you have 1 way to reach 5 from 4 but you also have 1 way to reach5 from 5

  • @ma-la
    @ma-la 2 ปีที่แล้ว +8

    Thank you! Great explanation. A slightly more compact code:
    one, two = 1, 1

    for i in range(n-1):
    one, two = one + two, one

    return one

    • @mayankbhola7325
      @mayankbhola7325 2 ปีที่แล้ว

      you don't even need "i" you can replace it with "_"

    • @Alex-mf3vo
      @Alex-mf3vo ปีที่แล้ว

      your example of the loop works and gives 8 with n=5, thanks! But I don't get why code in video
      for i in range(n-1):
      temp = one
      one = 1 + two
      two = temp
      with n=5 gives result 3 and not 8? As for me it should be the same 🤔

  • @GateSlasHendrix
    @GateSlasHendrix 3 ปีที่แล้ว +98

    instead of storing a temp variable, you can do this in python3+:
    one, two = one + two, one

    • @farmanguliyev
      @farmanguliyev 2 ปีที่แล้ว +22

      it also uses temp value in the background.

    • @AusTxMale
      @AusTxMale 2 ปีที่แล้ว +5

      Or use: "one = one + two" and then "two = one - two" to do the same thing without an implicit temp variable.

    • @gerhitchman
      @gerhitchman 8 หลายเดือนก่อน +1

      @@farmanguliyev yes, but the code is cleaner

  • @augusto2581
    @augusto2581 8 หลายเดือนก่อน +1

    Ok, hats off to you. The problem can be 'easy', but with your explanation of Memoization and bottom-up approach, you make this a 'must understand' problem. Thank you very much for all your efforts to explain it to us.

  • @prafulparashar9849
    @prafulparashar9849 2 ปีที่แล้ว +1

    Great video as always !!
    here is the recursion based DP approach in Python if anyone requires.
    class Solution:
    def climbStairs(self, n: int) -> int:

    # dfs appraoch
    def helper(n, index, memo={}):
    # base case
    if index > n:
    return 0
    if index == n:
    memo[index] = 1
    return 1
    if index in memo:
    return memo[index]
    # recursion case
    memo[index] = (helper(n, index+1, memo) + helper(n, index+2, memo))
    return memo[index]
    return helper(n, 0)

  • @megm9963
    @megm9963 3 ปีที่แล้ว +5

    Thanks

    • @NeetCode
      @NeetCode  3 ปีที่แล้ว +1

      Hey Meg, thank you so much! I really appreciate it 😊

  • @nicholascamarena6983
    @nicholascamarena6983 2 ปีที่แล้ว +52

    FYI there is a O(1) solution because there is a closed form expression for Fibonacci numbers. As in, there is an equation for Fn (the nth fibonacci number) that is only a function of n, instead of a function of Fn-1 and Fn-2

    • @spirosgalanopoulos2560
      @spirosgalanopoulos2560 2 ปีที่แล้ว +12

      Indeed, although I am not sure it is that easy to calculate the nth fibonacci number in constant time, because exponentiation takes O(logn). It is also worth mentioning that one would have to use the known matrix exponentiation algorithm for fibonacci numbers, to avoid precision problems that arise from exponentiation of irrational numbers. Either way, though, it is indeed true that this observation leads to a faster solution, nice.

    • @sb_dunk
      @sb_dunk 2 ปีที่แล้ว +2

      @@spirosgalanopoulos2560 When you say exponentiation, do you mean calculation of √5 and of the golden ratio constants?

    • @spirosgalanopoulos2560
      @spirosgalanopoulos2560 2 ปีที่แล้ว +7

      @@sb_dunk I was referring to ((1+sqrt(5))/2)^n.

    • @sb_dunk
      @sb_dunk 2 ปีที่แล้ว

      @@spirosgalanopoulos2560 Oh yes, of course!

    • @mensaswede4028
      @mensaswede4028 2 ปีที่แล้ว +2

      Yes exactly. In fact the original problem as stated, before any analysis is done, smacks of a problem that probably has a closed solution.

  • @classicwhispers391
    @classicwhispers391 3 ปีที่แล้ว +4

    Thank you so much for taking the time to explain this. It makes a lot more sense now.

  • @mercymutuku4525
    @mercymutuku4525 2 หลายเดือนก่อน

    I have watched this solution so many times and every time it amazes me the same. Love how you started with a brute force solution, made it better and finally made it waaaay better and simple. Helps to build a "thought process" and see the many ways of solving the same problem 🙏👏❤‍🔥

  • @aicancode5676
    @aicancode5676 3 ปีที่แล้ว +11

    For anyone who is confused why the base value is 1. I think we can try to understand better with this code, as we know that
    dp[2] = 2 and dp[3] = 3, we can just work our way up there. Hope this helps.
    class Solution(object):
    def climbStairs(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n

  • @TanakaNdove
    @TanakaNdove 8 หลายเดือนก่อน

    two years later, we are still learning! Brilliant. Thank you!

  • @fairozahmed6888
    @fairozahmed6888 2 ปีที่แล้ว

    I have watched it from many other TH-camrs, no one even comes near you...
    Crisp and clear... Very good explanation

  • @alimbekmaksytov
    @alimbekmaksytov 3 ปีที่แล้ว +9

    'just five lines' of but neat code. I appreciate your tutorials for easy-to-understand explanations

  • @itsZybn
    @itsZybn 2 ปีที่แล้ว +1

    The decision tree makes it so clear. Absolutely brilliant my friend!

  • @toooes
    @toooes 2 ปีที่แล้ว +5

    > always start with a brute-force recursive solution- the best way to start solving any DP problem, *then* apply memoization/tabulation techniques

  • @yizhang7027
    @yizhang7027 2 ปีที่แล้ว +1

    I love that you always start with a brute force solution, making the dp solution really natual in contrast.

  • @nameno7032
    @nameno7032 ปีที่แล้ว

    Been learning DP since for ever, only watch your videos can make me wrap my head around, big thanks

  • @sucraloss
    @sucraloss 9 หลายเดือนก่อน

    Great video! I still will need to rewatch this a few times I think, but eventually this will make sense.
    I get the memoization solution at least.
    For anyone looking for the memoization code, I copied this from the solution section but this will save you a few clicks:
    class Solution:
    def climbStairs(self, n: int) -> int:
    memo = {}
    memo[1] = 1
    memo[2] = 2
    def climb(n):
    if n in memo:
    return memo[n]
    else:
    memo[n] = climb(n-1) + climb(n-2)
    return memo[n]
    return climb(n)

  • @andresnet1827
    @andresnet1827 9 หลายเดือนก่อน

    Both, the way you explain and the animations you provide, are truly awesome!

  • @emmanuelcbenson
    @emmanuelcbenson ปีที่แล้ว

    Where have you been all my life? Thank you and thank you again. Words have failed. Thank you.

  • @justwanjiku
    @justwanjiku 2 ปีที่แล้ว +2

    You have a talent of explaining hard concepts easily. Thank you.

  • @jordiburgos
    @jordiburgos 2 ปีที่แล้ว +1

    This solution is very tied to the 1 and 2 steps. I would expect a more generic solution with different step sizes i.e. n=10, steps=1,2,5

  • @miguelescalantemilke7204
    @miguelescalantemilke7204 2 ปีที่แล้ว +2

    Nice way to look at problems.
    I started using some kind of combinatorics and modular arithmetic, and I was like "why is this a Fibonacci sequence?" And then I thought that it kinda made sense as the case n+1 was something like the solution for n plus the solutions to go from the n step to n+1 (sort of, I took a little time to better catch the pattern).
    But looking at it as a top to bottom problem made waaaay easier. And I'm not really used to the notions of storing results and looking at solutions as an algorithm instead of an equation really help me ace my future interviews. Thanks for the video. You just earned a subscriber :)

  • @CFATrainer
    @CFATrainer ปีที่แล้ว

    Neetcode will go down as a legend in programming circles.

  • @dusvn1484
    @dusvn1484 2 หลายเดือนก่อน

    I got this memoaization approach by my own but this bottom up is fantastic.
    You are genious!

  • @amanrai5285
    @amanrai5285 2 ปีที่แล้ว +1

    I'm getting OCD when I see you solved this without calling the orignal function back!.. Great work. Thank You.

  • @licokr
    @licokr ปีที่แล้ว

    Wow, awesome. When I see how Neetcode solve a problem, I feel it is really important to figure out a way to solve a problem. First try, I used bruceforce, and I watched this video 30% and I solved a problem using DP but still used recursive calls, I finished watching the explanation and it was A-ha moment and I solved the problem using an array, and I thought I did it well then I saw the code he doesn't even need an array. Awesome.....awesome...

  • @jakedickson697
    @jakedickson697 2 ปีที่แล้ว +3

    The beauty of this solution is that the question being asked is how many different routes, not what are ALL the different routes, hence the optimisation shown here. Fantastic work.

  • @tomasoon
    @tomasoon 2 ปีที่แล้ว +1

    to me, this is literally mind blowing, your explanation is perfect. thank you

  • @vladyslavkotov7570
    @vladyslavkotov7570 2 ปีที่แล้ว

    jesus, that array in the end was really the top anime plot twist of all time. fantastic explanation, my man, that's a sub right there

  • @saran703
    @saran703 3 ปีที่แล้ว +6

    man, you just made it eazzzz. Great explanation btw

  • @cpaulicka
    @cpaulicka 2 ปีที่แล้ว +3

    Thanks for the videos. Just wanted to remind you that you don't need temp variables if you do tuple assignment (ie one, two = one + two, one)

    • @smt210samsung2
      @smt210samsung2 2 ปีที่แล้ว

      I wait for this in video, bcause its very pythonic way

  • @kasamadhu3509
    @kasamadhu3509 2 ปีที่แล้ว +1

    first time listening about dynamic programming completely understood.

  • @deville295
    @deville295 3 ปีที่แล้ว +4

    you explain like I'm a dumbass and this is why I like it

  • @adityaparab797
    @adityaparab797 2 ปีที่แล้ว

    Great Explanation seriously. They way you break down the problem and optimise it step by step is just great! Thank you so much for making these videos.

  • @lch99310
    @lch99310 2 ปีที่แล้ว

    I cannot express how clever you are. Genius.

  • @rajwanahmed935
    @rajwanahmed935 5 หลายเดือนก่อน

    This is the best explanation I have seen. Thanks

  • @seza1231
    @seza1231 ปีที่แล้ว

    I love how intense the liner gets

  • @yassineboumiza1031
    @yassineboumiza1031 หลายเดือนก่อน

    i was taking an olympiad test in math and i found a problem very similar to this and i solved it because i've already seen your video.thanks

  • @anabildebnath2590
    @anabildebnath2590 7 หลายเดือนก่อน

    One of the best explanations I have ever heard.

  • @festooned
    @festooned 3 ปีที่แล้ว +2

    great explanation and so helpful for getting me more confident in DP problems!

  • @LowLevelLemmy
    @LowLevelLemmy 2 ปีที่แล้ว

    The ending was the biggest plot twist of my life. Thought it was going to be super complex. It's just 5 lines of cute code 🤣🤣🤣🤣

  • @magesh4806
    @magesh4806 29 วันที่ผ่านมา

    The explanation on memoization part was excellent

  • @kapildharao8321
    @kapildharao8321 3 ปีที่แล้ว +6

    Very nice explanation, I understood the whole concept of Dynamic Programming in one video. Thank you!

  • @nickolaskraus
    @nickolaskraus 2 ปีที่แล้ว

    nit: you can use tuple packing and unpacking for simultaneous state updates.
    Example:
    def fibonacci(n):
    x, y = 0, 1
    for i in range(n):
    print x
    x, y = y, x+y
    This removes the need for a temporary variable. Just a nit, thank you for all that you do.

    • @NeetCode
      @NeetCode  2 ปีที่แล้ว

      Good point!

  • @namelesslamp12
    @namelesslamp12 3 ปีที่แล้ว +6

    lol, i am currently completing the spreadsheet and I was surprised u didn't have a video of this problem so i google it and here it is. thanks bro really nice content

    • @rakeshakkannagari7559
      @rakeshakkannagari7559 3 ปีที่แล้ว

      Which spread sheet??

    • @singletmat5172
      @singletmat5172 3 ปีที่แล้ว

      @@rakeshakkannagari7559 this one docs.google.com/spreadsheets/...

  • @arshdhanani8936
    @arshdhanani8936 ปีที่แล้ว

    HOW CAN ONE BE THIS GENIUS OMGGGGGG WONDERFUL APPROACH

  • @hemavarthini8112
    @hemavarthini8112 ปีที่แล้ว

    The best ever explanation one could ever give. Thanks a lot!

  • @LsEagle18
    @LsEagle18 7 หลายเดือนก่อน

    My interest in programming after watching this video 📈📈
    Amazing explanation. Loved it

  • @huleboermannhule44
    @huleboermannhule44 2 ปีที่แล้ว +1

    If you looked a bit closer at it you would see that the numbers you get are the fibonnaci numbers. There is a closed form way to calculate any, without calculating previous terms. That uses the golden ratio, and is relatively expensive for small numbers, but dominates for large numbers

    • @justindion4394
      @justindion4394 2 ปีที่แล้ว

      Coming from an industry that relies heavily on number series, this was my first intuition as well

  • @tiendatnguyen6758
    @tiendatnguyen6758 2 ปีที่แล้ว

    This is crazy simple, man. Just love it 100%

  • @quicksketch1617
    @quicksketch1617 11 หลายเดือนก่อน

    Thank you, I watched another vídeos about the problem and it's the first explanation I saw about decision tree. Made me think different

  • @gopalchavan306
    @gopalchavan306 3 ปีที่แล้ว +1

    wow this is pretty awesome, really liked the way you break the problem

  • @er0s14
    @er0s14 10 หลายเดือนก่อน

    Wow...🤯 Thank you for the amazing explanation and experience, feels like Im back in college. Now im going to sit down for an hour and process it all

  • @sidazhong2019
    @sidazhong2019 3 ปีที่แล้ว +7

    this is a really good explanation!

  • @vedaantrath2946
    @vedaantrath2946 ปีที่แล้ว

    Your Decision Tree explained memoisation succinctly. Thanks !!!

  • @siruxsolutions
    @siruxsolutions 2 ปีที่แล้ว

    Honestly the best video about introduction to dynamic programming.

  • @tabassumkhan7498
    @tabassumkhan7498 2 ปีที่แล้ว

    To better visualise it, take a top down approach. For example,
    If it's 3, you have 2 decisions to make at every step to reach the bottom stair. Either you could take 1 step or 2 steps. So, the decision tree will look like this. The left edge represents 1 step and the right edge represents 2 steps.
    3
    / \
    2 1
    / \ / \
    1 0 0 -1
    / \
    0 -1
    So, when you reach 0 return 1 and when you n < 0 return 0
    Also, if you notice it is like the Fibonacci sequence 1 1 2 3 5 8 13....
    And then the memoisation is easy t reduce the time complexity

  • @MichaelShingo
    @MichaelShingo ปีที่แล้ว

    such a good explanation of a fundamental problem

  • @madanielmadaniel
    @madanielmadaniel 2 ปีที่แล้ว +1

    First of all, thanks once again for comprehensive and well done explanation about this problem 🥇 !
    Second, I had difficulties to comprehend the movement into the solution code it was just too fast for me.
    In addition I didn't understand why dp[n] == 1 and not 0 - since logically it's the target number, so we won't need to do more steps...
    As a suggestion, in case others will struggle like me, I think it's better to start with the recursive solution and to see how it's similar to Fibonacci solution.
    Then, trying to print solutions for n= 0, 1, 2, 3, 4, 5 and to see the pattern -> this explain why dp[n] == 1 - it's because we wrote the function to return 1 in case number == 0 and when we translate this to a loop, we want to init the first value into 1.
    Second value will also be 1 - run the recursive function (with debug prints) and see why.
    After you see the Fib pattern, all you need to do is to implement a fib loop to return the number as shown in the video.

    • @amandaflood
      @amandaflood 2 ปีที่แล้ว +1

      Thanks, that helped

  • @-seoulair
    @-seoulair ปีที่แล้ว

    Incredible incredible explaining. I really understood everything you said.

  • @MafiaXII
    @MafiaXII 3 ปีที่แล้ว +4

    I found it easier just looking at the three base cases and then deriving dp array/slice; one stair, two stair or three stairs.
    // 1 stair = 1 way
    // 2 stairs = 2 ways
    // 3 stairs = (take 1 step + sum of 2 stairs) + take 2 steps + sum of 1 stairs)
    // 3 stairs = (take 1 step + sum of 3-1 stairs) + take 2 steps + sum of 3-2 stairs
    // n stairs = (take 1 step + sum of n-1 stairs)+ take 2 steps + sum of n-2 stairs
    // n stairs = n-1 + n-2
    //golang
    // o(n) space and time
    func climbStairs(n int) int {
    if n == 1 {
    return 1
    }
    if n == 2 {
    return 2
    }

    dp := make([]int, n)
    dp[0] = 1
    dp[1] = 2


    for i := 2; i < n; i++ {
    dp[i] = dp[i-1] + dp[i-2]
    }
    return two
    }
    From here, you can optimize space to be O(1) instead of O(n) by realizing that you only need two-three variables to store dp[i-1] and dp[i-2], and d[i]
    //O(1) space and O(n) time
    func climbStairs(n int) int {
    if n == 1 {
    return 1
    }
    if n == 2 {
    return 2
    }

    previousStairSum, currentStairSum:= 1, 2

    for i := 2; i < n; i++ {
    previousStairSum, currentStairSum= currentStairSum, previousStairSum + currentStairSum
    }
    return currentStairSum
    }

    • @namoan1216
      @namoan1216 3 ปีที่แล้ว

      same as my idea, I think it is easier to come up with this solution

  • @perelium-x
    @perelium-x 8 หลายเดือนก่อน +1

    Here is the Top Down approach for anybody curious
    class Solution:
    def climbStairs(self, n: int) -> int:
    memo = {}
    def climb(m):
    if m in memo: return memo[m]
    if m == n:
    return 1
    if m > n:
    return 0
    memo[m] = climb(m+1) + climb(m+2)
    return memo[m]
    return climb(0)

  • @Aripoma
    @Aripoma ปีที่แล้ว +3

    Theres a reason why this video has so many views! its so good. I do have one question. I am confused why in the DP array why is 5 equal to 1? I understand its the base case but you also said there's one way to get to 5 from 5 but shouldn't it be zero? (12:15)

  • @mohammedfahadnyc1385
    @mohammedfahadnyc1385 2 ปีที่แล้ว

    Oh my god. You are a Gem. So clear and concise. Thank you neetcode.

  • @s8x.
    @s8x. ปีที่แล้ว +1

    Wow this was a great explanation. I love you ❤

  • @karan_deshmane
    @karan_deshmane 6 วันที่ผ่านมา

    One of your best works

  • @K4RD050
    @K4RD050 4 หลายเดือนก่อน

    Nothing easy about this 😅 except for the miraculous explanations of this channel as always! 🙏

  • @vanitaladkat1491
    @vanitaladkat1491 ปีที่แล้ว

    What an explanation, I am by default follower now ;) Thanks for such a great explanation.

  • @chatbot2.0
    @chatbot2.0 2 ปีที่แล้ว

    A much better and clearer explanation of DP than my algorithm course…

  • @akhma102
    @akhma102 ปีที่แล้ว

    Thank you, Neet. You make our lives easier!

  • @vyshnavijetti
    @vyshnavijetti 10 หลายเดือนก่อน

    this is a very interesting solution . it makes lot of sense now how programming make life simple

  • @andreasandres
    @andreasandres 3 ปีที่แล้ว

    Dude, i love that punch line in final 10 secs on this videos !!!!

  • @scpcomm1215
    @scpcomm1215 ปีที่แล้ว

    I couldnt stop thinking who came up with this algorithm. You go from a long manner of counting by ones and twos, to creating a decision tree, to finding patterns and see how can you simplify the code, to ultimately realizing that counting backwards can simplify the counting, to ultimately recognizing the solution is simply the fibornacci series of numbers. TOo easy, becuase some genius paved the way... amazing

  • @DarkWolfes
    @DarkWolfes 2 ปีที่แล้ว

    whilst storing the initial value of "one" totally works, setting two = one - two does not require the temporary variable.

  • @samarthgodase1011
    @samarthgodase1011 3 ปีที่แล้ว +3

    Amazing! Pls keep going your videos helps a lot Thanks :)

  • @machoman8940
    @machoman8940 2 ปีที่แล้ว

    Thanks neetcode! I'm a better person now because of your videos!

  • @srikika
    @srikika 3 ปีที่แล้ว +1

    this was so clean! love it! thanks for making the vid.

  • @snowcycle7
    @snowcycle7 2 ปีที่แล้ว

    Dude you’re a beast, you’ve been helping me so much thank you 🙏

  • @_ipsissimus_
    @_ipsissimus_ 3 ปีที่แล้ว +5

    this one was hard for me because I could easily do UNIQUE combinations, but thats not what the question asked for. It counts 122 along with 212 and 221 (for 5 steps) as valid combinations, even though they arent unique.

    • @bennbeckman7793
      @bennbeckman7793 2 ปีที่แล้ว +1

      I actually figured out a way to do it w/combinations. All you have to do is divide the number of steps you took, N, by the product of the factorial of each repeated number. So if you want to climb 7 steps, if you only take a 2-step once, it would look like 111112. Since 1 repeats 5 times and 2 only once, you get 6!/(5!*1!). Do this for the amount of times that you can take 2 out of 7 evenly and add them together. So 7/2 = 3.5 you would repeat that 3 times adding adding another two and removing the ones respectively.

  • @Ved3sten
    @Ved3sten ปีที่แล้ว

    This is one of those questions where the solution is so simple when you look at it when you look at the recurrence, but then you're in disbelief so you try to enumerate all the combinations

  • @avanishgvyas1992
    @avanishgvyas1992 3 หลายเดือนก่อน

    17:54: "We went through so much headache just to get to these 5 lines of code"
    Software Engineering in a nutshell

  • @maku_chan3997
    @maku_chan3997 3 ปีที่แล้ว +3

    Amazing. This is the best explanation I have seen for dynamic programming.

    • @NeetCode
      @NeetCode  3 ปีที่แล้ว

      Happy it's helpful 😊

  • @Ryan-xb1ry
    @Ryan-xb1ry 2 ปีที่แล้ว

    Thank you so much. This is the best solution I ever saw.

  • @AlexdeAbreu13
    @AlexdeAbreu13 ปีที่แล้ว

    Incredibly well explained. Thanks!