05 - More Climbing Stairs (Dynamic Programming for Beginners)

[@andreygrehov]

Next video: kzbin.info/www/bejne/baewkIWQeqyImdk Previous video: kzbin.info/www/bejne/h523ZXt9bph6l9k

[@martedesco]

Thanks for the doubly-linked list correlation to your videos

[@fridayameh4411]

I have watched a lot of tutorials on dp trying to explain this concept but I couldn't get hold of it. You really made my day even though you implement in go programming language the concept was well explained and I want sincerely appreciate the good work and the time you spent to put up this content. Thank you very much. You got my subscription.

[@sarveshkaushal4585]

This is best channel to learn DP. I have been struggling with dynamic programming since i started coding. I hope to learn it here now. Thank you very much.

[@naaawaaa]

As Go supports variables swapping, the code can be simplified as a := 1 b := 1 for i := 2; i

[@MrYurann]

Time could be optimized to be back to O(N) if you keep a running sum of dp[i-1] ... dp[i-k]. Then every time you evict the oldest element (dp[i-k-1] and add the new one dp[i - 1]).

[@ravishyam6951]

I am not able to figure out how time complexity gets any better by this. Can you share the code?

[@RaoVenu]

@@ravishyam6951 /* Target N where can climb 1..k stairs Time complexity O(N) Space complexity O(N). Can be reduced to O(K) if we care to optimize as at any time we care to have only k elements in the dp array This is a linear solution cause let us assume that we are interested in calculating dp[i] where i > k then we have dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[i - k - 1] + dp[i - k] dp[i + 1] = dp[i] + dp[i - 1] + dp[i - 2] + ... + dp[i - k - 1] So to calculate dp[i + 1], we see that most of it is repeated from the calculation of dp[i], hence dp[i + 1] = 2 * dp[i] - dp[i - k]; */ const climbingStairs = (N, k) => { const dp = [1, 1]; // 0, 1 base cases for(let i = 2; i k ? dp[i - k] : 0); dp.push(curr) } return dp[N]; }

[@mihirsidhdhapurasensei]

@@RaoVenu cool man i really like it.

[@jinhuang7258]

Thank you for sharing your knowledge and time! Your explanation is very clear and easy to understand, not trying to overcomplicate things.

[@StackJobs]

How nice this video is. If i hasn't meet with this video, I could have waste much of time on dynamic programming. Thank you very much, Subscribe absolutely.

[@chap_eau]

I will never thank you enough. great video and great playlist🎉🎉

[@Pangelicious]

Great video. Learnt a lot on how to approach these types of problems :) Thank you!

[@pratikaher4289]

Amazing. Loved it! keep up the good work. We don't mind your babies yelling at all :)

[@andreygrehov]

Haha, thanks!

[@stevendhondt771]

Don't you need to set 'c = 1' as well in the example of better space complexity, for the edge cases to be right?

[@charleslatrom7658]

The the first and second parts we stored the pointers as variables. I wonder if it would be ever so minuetly more efficient if these were stored in an array? E.g int[3] which stores a, b and c. This way cache locality may cache values in this array, as opposed to variables which may be sparsely populated across the memory stack. Although obviously this is very dependent on the language (I'm a Java engineer).

[@andreygrehov]

Yes, these are micro-optimizations one could do.

[@cutiex7357]

After this video I understood the previous one better! 😍 Going to watch the next one tomorrow 😁

[@woodylucas]

You could have still used, an array for 0(1) space. We could have created and array with only two indices lastTwo = [1, 1] and within our loop we could have a variable for example nextSteps which will be the sum of the first two elements within the array, lastTwo[0] + lastTwo[1] and then swap like you did there. Return statement will only have one an edge case, and that will be if n is less than 1 return the first element otherwise return the second. Overall it's still a great solution, just like to know multiple ways to solve problems--helps me conceptually.

[@andreygrehov]

Good job, @Woody.

[@dnc077]

thank you so much for thjis series - followed through from part 2. it's clarifying the picture of dynamic problem better to me... +1 subscribers :)

[@familywu3869]

Thank you for the lecture, Andrey. This is very helpful in understanding dynamic programming. I have a question, in your one coding example, when k=3 (allowed steps), you have a base case for f(2), in addition f(0) and f(1) (when the allowed steps are 1 and 2 only), but for the 1...k (allowed steps) case example, why base cases are still just f(0) and f(1) only? but not f(0), f(1), f(2) .... and f(k). Thank you.

[@frindle18]

Did you get the answer to this? Cuz I have the same doubt too

[@frindle18]

Nvm, got it. How it works is that the base cases themselves get calculated inside the for loop, since we're using a bottom up approach. So we need k base cases, but the calculation of base cases itself is a subproblem which gets calculated in the loop. For example, if k = 4, we need 4 base cases. f(0) = 1 is the base case provided. f(1) = f(0) is calculated in the for loop, so is f(2) = f(1) + f(0), since these smaller subproblems require smaller number of base cases with n = 1 requiring only 1 base case which we provide. So the k required base cases are getting built as we go along.

[@TheJinnyus]

Thank you so much for the video! I had a question about the function - if i=2 and j=1, and dp[2] += dp[1], then how would we know the value for dp[2] to keep incrementing? Since we only know dp[0] and dp[1], and dp[2] has to add onto itself?

[@andreygrehov]

Thank you. That's a great question. I should've covered that. dp[2] in this case is 0. In Go, if you create an array of integers, all of its elements by default are 0. In other languages you might need to set each value of the dp array to 0 first, and only then start the main loop.

[@TheJinnyus]

@@andreygrehov perfect!! I wasn’t familiar with Go. Thanks so much for the explanation :)

[@MukilShelby]

You're a legend!!

[@alexeybondarev7654]

Hi Andrey, I'm confused. The solution for the basic problem for n=1000000 should be astronomically huge number not the one you tested on so you need the huge memory just to store one such solution.

[@andreygrehov]

Hi Alexey. Yes, you are right. I should have avoided the n=1000000 test. I don't remember why I decided to include it, but it was definitely not a good idea. The result of climbStairsKSteps(1000000, 2) is indeed an astronomically huge number. The reason why it's not failing is because Go doesn’t check for overflows implicitly. In our case it simply operates in the range of MinInt64 to MaxInt64, so MaxInt64 + 1 = MinInt64. I'll comment this test out. Good catch. Thank you!

[@tusharroy6182]

Keep up the good work! Really helpful videos !! 😃

[@SajidAli-fn9tp]

Hi Andrey, great tutorial and demonstration. I could be wrong but I believe the "continue" statement at 10:35 can be replaced by "break" to make the program more efficient.

[@rafaelortega1376]

I agree

[@yizhang7027]

Could you please do a series on backtracking?

[@rafaelortega1376]

In the k version of the problem, you define only two initial cases. However it should be three for one of the test cases. Right?

[@supratikpadhee4235]

Hi Andrey , have one doubt , if we have at most three choices to jump. then total ways should be : 1. (Total_possible_jumps )C 1 + (Total_possible_jumps )C 2 + (Total_possible_jumps )C 3 + (Total_possible_jumps )C 4 + ---------------------------- (Total_possible_jumps )C (Total_possible_jumps - 2) + (Total_possible_jumps )C (Total_possible_jumps - 1) + (Total_possible_jumps )C (Total_possible_jumps ) = 2 ^ ( Total_possible_jumps) 2 . for every step , we have three choices to make . i.e = 1 jump , 2 jump , 3 jump so for N steps = 3 ^ N which of the thought process is correct ?

[@homertaki7633]

Could you explain me how its work dp[i] += dp[i-j] in loop that we got for example "In the 3 steps problem we do dp[i-1] + dp[i-2] + dp[i-3]" but not dp[i] + dp[i-1] + dp[i-2] + dp[i-3] ? What this mean in the loop dp[i] += dp[i-j]? It is dp[i] =dp[i] + dp[i-j] ? I think it is not because we received dp[i-1] + dp[i-2] + dp[i-3] but i do not why.

[@andreygrehov]

> dp[i] + dp[i-1] + dp[i-2] + dp[i-3] That is correct, but dp[i] is always 0, since its value is not known yet, so we end up with dp[i-1] + dp[i-2] + dp[i-3] .

[@hil449]

yea, in c++ you'd have to initialize dp to zero with dp[n+1] = {0}

[@vsvinuraj1982]

looks like we need to initialize c to 1. otherwise we will get the wrong answer when n =1?

[@EsotericArnold]

darn it, I got this half right. I knew the ...k would indicate a second loop but I messed up by assuming it was the same dp[i] = dp[j-1] + dp[j-2] :( glad i was able to see the solution. dp[i] += dp[i-j]. I completely understand thaat this expands to dp[i] = dp[i] + dp[i-j] where J represents the k step.

[@coolmaster-gh3tr]

why is f(3) not a base case? wouldn't it be simple to do because it would only take 1 step?

[@onemanenclave]

10:59 You got your last testcase so wrong. The correct answer for n=(a million) and k=2 is a MUCH bigger number (ENORMOUS, in fact), which takes like 10 seconds of full CPU usage to compute. And if you don't delete the numbers you no longer need from the array as you go, it ends up eating up all your RAM and fails to run to completion. Just to give you an idea of how off your expected number is for n=(a million), if you run it just for n=4555, you get a number with 952 digits.

[@andreygrehov]

Yea, you are correct. Don't know what I was thinking about. Good catch. I believe that last test case I quickly verified somewhere and then added it without giving much thought.

[@glensee7506]

I love it, thanks!

[@stuband4159]

Is the program climb n stairs using k steps designed to be a general solution for just the values of k=1,2,3 ? Maybe I have hugely missed the point here as it only appears to work with those. For example with n=4 and k=4 the program returns the value 8, but there are only 7 ways to climb 4 stairs using step of lengths of 1,2, 3 and 4, they are: 4 x 1 2 x 1 and 1 x 2 1 x 1 and 1 x 2 and 1 x 1 1 x 2 and 2 x 1 1 x 3 and 1 x 1 1 x 1 and 1 x 3 1 x 4 In general to solve a linear k order recurrence relation you need k base cases, you have only given 2; the program works for 3 because of fortune really, but breaks for 4 onwards. Obviously for a k order recurrence relation a closed form formula exists meaning you can go straight to the solution without any iteration but for nonlinear systems this is not always the case so a dp algorithm is very useful.

[@andreygrehov]

play.golang.org/p/FD2112WMb6V ibb.co/7rXd2jn

[@stuband4159]

@@andreygrehov You are right I have forgotten the 2x2 step.

[@alex_aleluia]

thank you so much

[@pranavkumar7369]

dp[i] = dp[i-1]+dp[i-2] // this is for 2 steps dp[i] = dp[i-1]+dp[i-2]+dp[i-3] // this is for 3 steps then dp[i]+=dp[i-j] means dp[i] = dp[i]+dp[i-j] ? so, if i =2 and j =1 then dp[2] = dp[2]+dp[1] but, here we don't know dp[2], how does it compute dp[2] ? Please explain this step.

[@praveengupta443]

intro music at 1.25 playback speed 🤩

[@namitpiriya]

a.w.e.s.o.m.e 😃😃 thanks for making this videos

[@harinagarajuvelivela5591]

Hi Andrey, can you please provide the solution for how space optimization can be done with O(k) as well.

[@andreygrehov]

I'll take a look into it.

[@MrYurann]

Use a dequeue, every time add new element in and delete the oldest once capacity is > k.

[@harinagarajuvelivela5591]

@@MrYurann sure, I will. Thank you.

[@harinagarajuvelivela5591]

@@andreygrehov Sure Andrey, Thanks.

[@JamshadAhmad]

@@MrYurann Great. That will work.

[@shrutiagrawal6065]

I guess if we can i start from k then it will work and want to know why you did i-j ?

[@andreygrehov]

shruti, i-j is a general form of the climbingStairs problem. So, in the 2 steps problem, we do dp[i-1] + dp[i-2] This ^ can be rewritten with the help of a for loop: for j := 1; j

[@ishu4696]

Waiting for you next video. please upload .

[@andreygrehov]

The new video is up: kzbin.info/www/bejne/baewkIWQeqyImdk

[@chathurapalihakkara9939]

Once a person comes to F(n-1) or F(n-2), He has to still climb one more step. So why its not F(n) = F(n-1)+1 + F(n-2)+1 and Instead F(n) = F(n-1) + F(n-2) ?

[@StatsByAdam]

Because i believe for each of F(n-1) and F(n-2) there is only one way to reach n by a 1 and 2 step respectively. For example for F(n-1) this is the number of ways you can reach F(n-1) and from that point there is only ONE way to reach F(n) and that is by a 1 step so that will increase the number of ways because there was not a choice at F(n-1)

[@wareeffallatah1335]

why isn't the time complexity O(n^2) time ?

[@TasneemAlEmam]

why should it be like that? you need 2 for loops the outer one with O(n) the inner one with O(K) so it should be O(n)*O(K) which is O(N*K)

[@wareeffallatah1335]

@@TasneemAlEmam thank you

[@tusharroy6182]

why are we doing "dp[i-j"] ?

[@andreygrehov]

Tushar, i-j is a general form of the climbingStairs problem. So, in the 2 steps problem, we do dp[i-1] + dp[i-2] This ^ can be rewritten with the help of a for loop: for j := 1; j

[@tusharroy6182]

@@andreygrehov Thank you so much! Your way of explanation 👌

[@supratikpadhee4235]

""" CLIMBING STAIRS AT-MAX 3 STEPS at one time, Total ways to reach the Nth step, if we can jump 1 , 2 , 3 steps at a time. 3 3 3 3 _______________ * _____________________ * ________________________ * ______________ = (3 ^ N) objective function : calculate the total no of ways to reach Nth step. To reach Nth step , we need to make some jumps. Njumps NC1 + NC2 + NC3 + NC4 + NC5 --------NCN = (2^N) recurrance relation : Count_ways(n) = Count_ways(n -1) + Count_ways(n -2) + Count_ways(n -3) base-cases : n = 0 --> Count_ways(0) = 1 n = 1 --> Count_ways(1) = 1 n = 2 --> Count_ways(2) = 2 order : bottom-up Where to find the answer : Count_ways(n) """ """ CLIMBING STAIRS AT-MAX K STEPS at one time, Total ways to reach the Nth step, if we can jump 1 , 2 , 3 -----K steps at a time. objective function : calculate the total no of ways to reach Nth step by making 1 ,2,3,4 ---- K jumps at one time. To reach Nth step , we need to make some jumps. N jumps Recurrance relation : Count_ways(N - 1) + Count_ways(N - 2) + Count_ways(N - 3) ----- + Count_ways(N - k) base case : 0

[@yizhang7027]

Isn't that a fibonacci sequence.

[@TasneemAlEmam]

yes

[@DaudZaidi]

When is the next video coming? Two days late already :P

[@andreygrehov]

Sorry mate, today-tomorrow! I was out of town.

[@DaudZaidi]

​@@andreygrehov No worries :) Take your time. Eagerly, looking forward for your next one.

[@ztrixx3280]

😀👍 awesome

[@olorunfemidaramola5470]

Use a map

[@louysatv]

Javascript O(nk)? const stairKSteps = (n, k) => { const arr = [1, 1]; // put k numbers from index 0 to index k - 1 to arr for (let i = 2; i < k; i++) { arr[i] = arr.reduce((p, c) => p + c, 0); } // find n for (let i = k; i p + c, 0); if (i === n) return arr[i]; } };

[@ConernicusRex]

In Swift: public func upstairsPaths3Step(_ stairs: Int) -> Int { guard stairs != 0, stairs != 1 else { return 1 } guard stairs != 2 else { return 2 } var db1 = 1 var db2 = 1 var db3 = 2 for _ in 3...stairs { let db4 = db1 + db2 + db3 db1 = db2 db2 = db3 db3 = db4 } return db3 } public func upstairsPathsKSteps(n: Int, k: Int) -> Int { guard n != 0, n != 1 else { return 1 } var dp = [1, 1] for i in 2...n { var sum = 0 for j in 1...k { if i - j >= 0 { sum += dp[i - j] } } dp.append(sum) } return dp[n] }

[@vzlomer1000]

Привіт з України )

[@andreygrehov]

Вiтаю!