11. Top-Down vs. Bottom-Up (Dynamic Programming for Beginners)

[@ShabnamKhan-cj4zc]

Best video found for dynamic programming.You explained the problem with real-time example and that's what is needed to understand any concept..Amazing work done.. A big thanks for your effort.

[@brycecullen3183]

Amazing explanation. The comparison of the three Fibonacci functions finally made the differences between top down and bottom up "click" for me.

[@Snakes.StartToSing]

I was confused with all the naming and which was which , top down, recursion, hash table, etc....you made it super easy to understand , thank you Andrey

[@mimi444-h8q]

brilliant! Love your way of teaching ,this series is amazing.

[@andreygrehov]

Thank you! Enjoy!

[@shatadruroy3926]

Andery! You are really amazing. These videos have taught me how to approach dynamic programming problems! Please continue this great work. This channel will get the recognition it deserves

[@baqirhusain5652]

Thank you .. beautiful consumable explanation ... interestingly I was using all the approaches unknowingly what they were called explicitly. Thanx

[@chun-yikuo7032]

Brilliant Series!! MILLION THANKS to your effort!!

[@algoseekee]

Andrey, thanks! Keep going 👍

[@andreygrehov]

Thank you, Viktor!

[@DavidCastro-sn3iy]

Andrey! just passing by to say THANKS! such an amazing content. DP has bee none of my improvement areas for quite a while, always trying to figure out how it's done and how it works through coding examples but not as clear as you do it in your videos and with the amazing framework you designed. Keep up the good work!!!

[@אופירמטוטי]

andrey im so happy that i found your channel . keep going!! your content is absolutely the best that i have seen for DP problems

[@ritikapande21]

These are some amazing videos of the problems which look more like mathematical problems and I had often wondered where to begin solving them. I have been binge watching your videos and believe me these are more enjoyable than Netflix series.

[@andreygrehov]

Haha, thanks a lot, Ritika!

[@bushigi5913]

This is exactly what we need for learning DP!!!

[@andreygrehov]

Hehe, thank you!

[@CharanRai]

Hey Andrey! Thank you so much. Your explanation is top-notch!. brilliant.

[@ashwinbabu007]

can someone explain the bottom-up backward : lets say n = 3. in the first iteration we would have to calculate:- dp[2] = dp[1] + dp[2] and dp[3] = dp[1] + dp[3] It doesn't make sense to me cos we haven't calculated dp[2] and dp[3], won't it throw an error? Please explain.

[@louysatv]

did you find the solution for that? it doesn't work for me either: const fib = (n) => { const dp = [0, 1, 1]; for (let i = 1; i < n; i++) { dp[i + 1] += dp[i]; dp[i + 2] += dp[i]; } return dp[n]; }; fib(8) return this array: [0, 1, 2, NaN, NaN, NaN, NaN, NaN, NaN, NaN]

[@SonLe-mi9xy]

In Go, when you declare an array, all initial values are automatically set to zero. However, in some other languages, you may need to initialize these values to zero manually.

[@BenNelsonillegalnumbers]

Great video! Looking forward to the next. Where did you get that cardigan! Fresh.

[@andreygrehov]

Thank you, Ben! Next videos are coming early September, as soon as I'm back from Europe. Haha, this is a Polo Ralph Lauren cardigan. Thanks for the compliment 🙌

[@StackJobs]

They say that bottom-up dynamic-programming is the real dynamic programming, and the top-down dynamic programming is just a recursion plus memorization. 👍

[@9fxhrlif9er]

Thank you so much for this Andrey! I have both liked this video and subscribed to your channel so you get more exposure!

[@SuperRalphinator]

Beautiful! I just commented about covering this on your previous video and you already did. I just hadn't got that far yet.

[@andreygrehov]

Appreciate it, Ralph!

[@xxRAP13Rxx]

Thank you so much for your video Andrey! I did have a few questions: at 6:35, you say top-down dynamic programming is "memoization + recursion". I don't think you said this in the video, but would bottom-up dynamic programming be "tabulation + iterative" (i.e. all bottom-up approaches can only be done with an N-D array and NO recursion)? Could top-down programming be done iteratively with memoization and NO recursion? Could bottom-up programming be done with memoization and/or recursion? I take it ANY dynamic programming approach MUST use at least memoization or tabulation to easily recall previous results?

[@andrewthompson4148]

this literally explained all of mainstream media

[@chunghosong7904]

Best DP videos in KZbin. just subscribed your channel, and waiting for more DP videos. Keep up the good work!

[@linhvu9638]

fantastic explanation, many thanks

[@elinorkent7188]

that was super helpful. really cleared up a lot of things for me.

[@pranavsingh1081]

Clear explanation which my prof could not teach me

[@jinhuang7258]

Fantastic video! Thank you!

[@Metachief_X]

brilliant explanation, thank you!

[@blasttrash]

nice series. do u plan to upload other videos?

[@andreygrehov]

Yes. I'm traveling until end of August. I'll get back to work as soon as I'm back. We have a lot more to learn.

[@stuband4159]

Even faster, but not using dynamic programming, is to use Binet's approximation which is f(n) = nearest integer to golden_ratio^n / sqrt(5) where golden_ratio = 1.61803398875 it's an irrational number but that value will do the trick f(20) = 1.61803398875^20 / sqrt(5) = 6765.000029572719 so the answer is 6765

[@sumodbadchhape9823]

Very helpful 👌 can you cover one of the most difficult problem the egg drop problem? Find the minimum number of egg drops to find the non breaking floor ?

[@yashtibrewal4259]

Thanks, I just watched the first half of the vid, the theory is what I needed, you want wanna split the videos into... double views ;)

[@shivamtyagi9936]

Andrew Ng and now u !!!! Great work

[@Ploofles]

Thank you so much I really needed this

[@JasonLee-pr4sx]

A better top-down solution, to reduce the times of entering function(stacking), to use the array to replace f(n-2). int fibo_seq(int n, int * arr) { if(n>2) { arr[n]=fibo_seq(n-1,arr)+arr[n-2]; } else { arr[n]=arr[0]+arr[1]; } return arr[n]; } Fibo_seq=new int[N+1]; Fibo_seq[0]=0; Fibo_seq[1]=1; fibo_seq(N,Fibo_seq);

[@pl5778]

Hi Andrey just came across you channel and your DP lessons are awesome! I had a question - is dp[0] = 0 or is it dp[0] = 1? I think you had both in various videos. If it is 0 i understand why, but what if its 1 what is the explanation? thanks!

[@andreygrehov]

The dp[0]=0 vs dp[0]=1 usually depends on the kind of DP problem you are trying to solve. When it comes to minimization problems (questions like: what's the minimum number of.....) then dp[0] is most often 0. When it comes to counting things (questions like: what's the number of ways to do ....) then dp[0] is most often quals to 1. Try to solve a few more basic DP problems and point your attention on base cases.

[@suchitragiri4546]

Very nicely explained!

[@Benjamin-Chavez]

Wow. Thank you, this is so helpful!

[@andreygrehov]

Glad you liked it, Ben. Thanks for watching.

[@shaoronkantor7619]

in fibBottomUpDpBackward you overwrite dp[i+1] on next interation. It would be better to use i = i + 2

[@zt_yang]

Thanks for your great work, please keep going~

[@iamgirraj]

Thanks Andrey...❤️

[@meganfoxyou]

Great video!

[@juncheng5945]

Great explanation.

[@andreygrehov]

Thank you, Jun.

[@andreygrehov]

Hey guys, I'm traveling in Europe, getting back to NY at the end of August. New videos are scheduled for early September. Sorry for the inconvenience, but I haven't seen my family for 3+ years. Stay tuned! Can't wait to get back to work! Next video: kzbin.info/www/bejne/f6KklZt-pbeoabs Previous video: kzbin.info/www/bejne/g4S1hX-wf6mZl8k

[@recoveryemail1046]

Огромнейшее спасибо за ваши старания!

[@adrianchandler6511]

InstaBlaster...

[@baqirhusain5652]

I reallly hope to get to your level where I make no syntax errors or logical errors....One Day

[@rishikeyyadav5717]

Great explanation..

[@pranavgupta93]

Hey Andrey, Thanks for making DP interesting for us. Your videos are awesome!!. Can you please help with the problem statement Given an integer N number of stairs, the task is count the number ways to reach the Nth stair by taking 1 or 2 step any number of times but taking a step of 3 exactly once. Similar to what you have covered in previous videos but can only take 3 steps one time only. Whats should be the logic behind this.

[@andreygrehov]

Hey, I think one way to solve this problem is by keeping track of how many times 3 steps were taken. I haven't checked if the answer is correct, but check it out: play.golang.org/p/D6tMjqS76ms k represents the number of times dp[i-3] was calculated. Try to draw the staircase on a piece of paper and solve the problem manually. Let me know if the code is correct.

[@nicholasdavis9529]

Why is line 79 and 80 not: dp[i+1] = dp[i] + dp[i-1] dp[i+2] = dp[i] + dp[i+1] or even just dp[i+1] = dp[i] + dp[i-1]

[@glensee7506]

I love it, thanks!

[@lyubomirgrozdanov914]

WHere did you read all of that?

[@mohamedhussien4013]

Thank u so much 🥰🥰🥰.

[@karankanojiya7672]

Respect++

[@okigan]

7:40 - “Top down DP is just recursion + caching” - this has been bothering me all the time - that is so much simpler to explain yet it is buried in layers and layers of over complex acrobatics.

[@melvin6228]

Sooo.... When are you going to talk about the cool applications of DP? :D You said yourself you needed it for a real world use case. I presume you've seen this one as well: avikdas.com/2019/05/14/real-world-dynamic-programming-seam-carving.html I think people would appreciate it when that gets turned into a video (when you believe you're at the right level for it in your series)

[@andreygrehov]

Hey @Melvin, yea, I've seen this article before. It's amazing. Real world applications is something I'm going to cover at the end of the course, right before we jump into Advanced Dynamic Programming (which is prob worth releasing as a separate course).

[@renkuro1221]

Please get a new marker

[@pisanghangus2]

You need to invest in a new marker pen haha

[@pisanghangus2]

but really good video explaining top down vs bottom up approach in dynamic programming.

[@andreygrehov]

Haha, I hate these markers. Good call.

[@waytospergtherebro]

Whatever kind of processing you're doing to pronounce English words isn't working at all.