Dynamic Programming lecture #1 - Fibonacci, iteration vs recursion

[@Errichto]

Fibonacci - leetcode.com/problems/fibonacci-number/ Staircase - leetcode.com/problems/climbing-stairs/ Min-Path Grid - leetcode.com/problems/minimum-path-sum/ Count-Paths Grid - leetcode.com/problems/unique-paths/

[@ivantishchenko4686]

Thank you for posting the links. It's a great way to understand the content!

[@evayang1398]

I'm trying to figure out the followup of the stair problem with limitation on max k jumps. I would think do[I][j] as ith stair with at most j steps, then dp[I][j] = dp[i-2][j-1] + dp[i-1][j-1], and dp[n][k] will be final answer. however, there are a lot of constraints, e.g.: if j > i, dp[i][j] should be same as dp[i][j-1], because it doesn't make any sense if add redundant 1 more step. and code is like: def stair2(n, k): if k == 0: return 0 if k < n/2: return 0 dp = [[0] * (k+1) for i in range(n+1)] for i in range(1, k+1): dp[0][i] = 1 dp[1][i] = 1 dp[0][0] = 1 for i in range(2, n+1): for j in range(1, k+1): if i < j: dp[i][j] = dp[i][j-1] continue dp[i][j] = dp[i-1][j-1] + dp[i-2][j-1] return dp[n][k]

[@ayoubed-dafali1904]

You're the best

[@abdurrahaman388]

Can u please clarify what is the optimised way to find Fibonacci numbers

[@lijiayi0921]

Others : make a 30 minutes video with 10 seconds of usefull stuff, and add a click bait title Errichto : "Consider changing the speed to 1.25". Meanwhile the whole video is priceless

[@pranavgawade1546]

Any of the FANG companies will throw thousands of dollars to have him as an employee. Still, this guy here is making free youtube tutorials for us as well as constantly contributing throughout the community. I just want to know how? Thanks a lot!

[@nonefvnfvnjnjnjevjenjvonej3384]

because faang and money can go fuck itself

[@MGtvMusic]

@@nonefvnfvnjnjnjevjenjvonej3384 xDDDDDDD

[@treyquattro]

more like millions...

[@AB-fc8io]

Because your passion and attitude is more important than millions dollars from FAANG

[@carlosdanielvenegas6559]

I think he works at a FAANG

[@alexneagu4466]

Hats off for you Kamil! With every video you succed to teach new things, and to inspire future programmers. I literally can't wait for some new vids from you.

[@ajr1791ze]

same here.

[@praveen3123]

Loved your interview with JomaTech!! I am here after that.

[@vladespinozacatacora9421]

praveen s me too

[@someonlinevideos]

I’m here similarly after one with a google engineer mock interview. The way he explains his thought process is super cool!

[@II_xD_II]

:O same how tf is it possible

[@vladimirmakushkin9453]

I really appreciate that you're describing the way to approach DP problems. Many other channels just give solutions to specific problems, which does not really help to build the intuition. Your explanation is amazing, thanks!

[@UnicycleSoul]

Mate, the way you explain dynamic programming is so much better than anything else I've heard from my professors, etc.

[@vedantsharma5876]

The efforts you took to add captions show your dedication to articulate your content greatly. Thank you Errichto, this is the best dp tutorial I've come across and I've watched plenty!

[@Elon..Musk.X]

I did my computer science degree a decade ago. Now i could only wish and dream if i had a teacher like you. Crystal clear N to the point explanation.

[@MrLuke255]

Honestly, you're explanation is way better than the one I was told at the university. Thanks! :)

[@jimmorrisshen]

Very true. Will share this video with my students.

[@iTrustInTheMusic]

luckily your uni actually taught you this....

[@yoyobunt]

watched this video 1 year ago and still remember how hard it was but you make it easier to think/approach the problem with the good analysis

[@valdius85]

Great job! I am so happy to see Polish coders showing up on the world stage strong. After choosing the wrong degree (Civil Engineering) I am now studying programming. This channel will help me with that. Best wishes from Polish living in Tokyo. I really hope to visit my home country on a business trip one day. One of my friend in Gdańsk is already working for a Japanese company so it is a realistic dream ;) Dziękuję za ciężką pracę i twój czas ;)

[@bhargavreddy7038]

polish coders are regarded as one of the best in india .

[@valdius85]

@@bhargavreddy7038 Thank you for sharing it.

[@jdiaz8933]

The value per minute of these videos is incredible. Thanks so much for putting the time to do this. God Bless You.

[@dumdumbringgumgum2940]

this is the best explanation of DP under 20 mins covering popular topics 👏👏👏👏 Thank you

[@cactusbee8474]

@Errichto 13:28 subtitle should be : And every state you compute in constant time, dp[i][k] = dp[i-1][k-1] + dp[i-2][k-1] + .. dp[i-k][k-1]

[@therealsey]

The maximum-path sum problem was impossible for me to understand up until 19 minutes and 46 seconds ago. Thank you Errichto!!! If I happen to make it past my coding test on May 11th, I will owe it to this lecture series.

[@alexcipriani6003]

Thanks for these videos dude, I learn more on this channel than I learn in a top tier university in CS in US.

[@samarthgupta9983]

Yet another amazing video. After watching the video, I was thinking of couple of problems ( modified versions of min path ). Problem 1: Given NxM grid with integer values. Let P be any path from top left corner to bottom right corner. We define F(P) as maximum value along the path P, i.e. F(P) = max{ a[i][j] | (i,j) belonging to P }. Find such path P* such that F(P) has minimum value at P = P*. You can only move down or right. Problem 2: Given NxM grid with integer values. Let P be any path from top left corner to bottom right corner. You can only move down or right. We define F(P) as number of times you changed type of move. More exactly, F(P) = number of points in P such that ( previous point is up and next point is right ) or ( previous point is left and next point is down ). Find such path P* such that F(P) has minimum value at P = P*. EDIT: For problem 2 obviously the answer is F(P) = 2 when you just go all right then all down or vice versa. Let me add, there is also K given. You have to find such path P such that F(P) is atmost K [ F(P)

[@samarthgupta9983]

@Errichto Congratulations on 10k subscribers. Really awesome milestone. Also, I think you missed my question. Can you please share your ideas?

[@SanjeevSingh-lg2sb]

Thanks Errichto for your channel. It is helping me personally. You are doing one of the best things for all the budding college students and engineers. I hope you continue your effort. Love from India.

[@drzewo3713]

Dynamic programming Lecture #0 : Intro : 0:05 When do we use DP ? : 0:45 Iteration vs Recursion : 1:44 Fibonacci Series : 3:39 Factorial : 7:36 Stairs : 8:33 Minimum Path Sum : 14:04 Summary : 18:01

[@victorariasvanegas7407]

I come from the Joma channel, you're really incredible, I'm new in this world, and I hope to learn a lot from your channel.

[@MrDivad006]

Please make a playlist where you solve leetcode questions. Just record yourself solving the leetcode questions: make one video per question (you solving it and commenting on the problem/solution), put the video into a playlist, and repeat for as many problems as possible. This would attract so many more people to your channel

[@CS-lk7ym]

hey errichto! These videos are awesome and best

[@peteco7417]

Also brought from JomaTech Video, I'm just here because I admire your attitude and willingness to share. I don't plan on making this a career but instead use as a tool to challenge myself to churn solutions to problems. Thank You

[@ManishSharma_msinvent]

Errichto thanks for putting this up. This is as precise as it can get.

[@BlockDesignz]

No one else made me understand DP until you came along

[@Errichto]

:)

[@CrystalSergeant]

pure gold. looking forward for next video

[@chikajinanwa9179]

Great video Kamil. I particularly enjoyed your explanation about dimensions of the state and transitions. Thank you very much!

[@AbjSir]

Dimension of dp is the number of variables which can completely define a state

[@sauravpaul4131]

Best tutorial about dp so far .Thanks.

[@aiman_yt]

I'm convinced Errichto was sent by God

[@parthmaheshwari2186]

Great Insights on how to approach dp problems. I request for more dp content as it is hard to get comfortable with.

[@ankitbansal2303]

Thank you, your videos are purely based on content quality and that's the best part.

[@avishekdutta1901]

Huge RESPECT to u Sir!!!! Please dnt stop and keep doing the good work....

[@pushkarsoni8927]

Seriously quality of information is very good

[@lovleshbhatt7797]

This video is Gold For understanding the dp working.... LOVE YOU BRO FROM INDIA....

[@vamsikrishnavalluru611]

Lovely methods man! Can you make a lecture series on how you approach different levels of Graph Theory problems? For examples how you solve DFS/BFS based problems, then Djikstra's Algorithm, Topological sorting, min-cut max flow ... and so on? I ask this because a lot of us know this in theory but its very difficult to implement solutions in a competitive coding contest.

[@bhargavreddy7038]

if you explains topics like this in such a less time , i don't think i would want to look for any other instructors for all other algo ds topics . Please make videos on all algo ds topics . Your videos will become go to videos in future for everyone. ♥️

[@Errichto]

Thanks!

[@watansahu2190]

Sir I'm really glad to have come across your videos,earlier I had came across the FFFTTTTT for binary search explanation in textual tutorials but always felt it hard to make sense, thanks for your such crystal clear detailed explanation that brought such clarity. I wish you could make tutorials on matrix exponentiation and how its used for DP . And just one wish that you also make similar video tutorials on Trees and Graphs and with links from where to practice them.I would be really grateful since Im preparing for interviews it would be of great help. Thank you sir..

[@surajnehra3031]

Hi Kamil i am a great fan of yours. I watch all your videos and you are my motivation for competitive coding. I wish you all the best for this codejam 2020.

[@amritbhardwaj99]

Very precise and clear Explanation Kamil!!

[@slyace1301]

Thank you so much for this man, I've never been able to perceive recursion

[@avinashchaubey8361]

thanks... a lot for such video lectures it really helps a lot eagerly waiting for next dp lecture with some interesting problem

[@samarth319]

Thank you kamil! Please make a video on Graph Algorithms as well. Really appreciate it.

[@sudhamani5149]

Wow! This video has made dp much easier for me. I find this extremely helpful. Thanks to you!

[@ManojKumar-hj7fh]

Hello Errichto, it would be great if you could do a series on recursion and how to think of an approach to write code for recursive problems, it can be useful for solving trees, strings, graphs and dp and a lot more, do consider making vidoes on recursion Thank you for the knowledge

[@Vivek.Rathi.53]

Very nice video sir. There is always something to learn from your every video.

[@stilllearning5982]

Thank you for the video. It helped a lot to know how to think to reach a solution for DP

[@swapnilmeshram9991]

Thanks for this awesome video. I was able to solve all four problems. Previously I got the min-path problem in an interview.

[@Chandansingh374]

Thanks for dp lec😀, please upload more such tutorial.

[@doodo_1]

Thanks for the video, I was facing problems while learning dp ,I saw half of the video and was able to solve all the four problems.

[@that_funny_guy496]

Thank you so much Errichto, your explaining style really helped me a lot.

[@ankishnayakcs0196]

I was really struggling with dp and your videos helped me allot . Thanks

[@LordLobov]

Thank you very much Eric, i've been struggling with DP a lot

[@danielk8452]

Thank you just made the DP really easy to understand when and how to use

[@LogicEu]

This is an incredible learning resource, thank you!

[@raghav4711]

@errichto: in the last minimum path sum, shouldn't we take the minimum of the previous of the two values (left and top) instead of the maximum?

[@Errichto]

Yep, you are right. I corrected it in captions but the video will stay with this mistake forever :D thanks for noticing!

[@Errichto]

@Tyler Durden How? In KZbin editor, I only see an option to add blur.

[@Paradise-kv7fn]

@@Errichto or you can pin this comment chain to the top

[@anarbay24]

@@Errichto I think it is possible, since in this video, you already corrected one mistake, where you put "*Space" word in the video

[@alihamdar5916]

finally someone made dp looks simple.. this will help me alot thx

[@xbz24]

high quality content as always errichto

[@ahmednesartahsinchoudhury2628]

Great video! Hope you make many more of these.

[@yehah]

Great video. Didn’t need subtitles as what you said is clear.

[@ouyaah]

Clear explanations and nice graphs, thanks!

[@shrad6611]

first time I saw you talk so much great explaination sir errichto

[@Qwantopides]

Thank you Errichto! I have known how DP worked, I could apply it, but I didn't really understand it. By that I mean, that some dots haven't connected in my head yet. Like what you have shown here. What is the real reason behind doing it. What if you do it differently. How does the method extend in certain scenarios. You have managed to explain this very simply, for which I thank you sir. :)

[@AbjSir]

dp is used to save time which gets wasted into doing repeated work Generally this happens when one state depends on more than one state

[@geoffl]

Now I understand!: - I watched this 3x - did the problems you linked

[@cakdham4607]

Genius, you have best explanation with straigh to the point

[@JL-pg4pj]

Please next time add some simulation of dp array by creating a box with every medium/hard problems. It will be better to understand for us in less time.

[@abeshekr7308]

Great video on dp! Hoping to see many more videos about competitive programming

[@malefetsanelenka8013]

Best explanation ever.

[@chatrughanprasad7778]

Absolutely Gold...about solving dp problem

[@tritranminh2808]

Really, thank you so much, it does help a lot.

[@MehbubulHasanAlQuvi]

This is what I've been looking for

[@ariabanazadeh1016]

Hi Thank you for your amazing lecture and please in other lectures go throught some code forces dynamic programming questions beacuse there is a lot of cllasical dp toturials but i dont think there is a lot about dp in code forces problems.

[@RHCIPHER]

You are good i'm a future engineer i wish to be successful as you

[@tagberli]

the most chad intro

[@donbasti]

Amazing channel !. Would love to see some Discrete Math and Graph Theory :)

[@alexwindy3]

Wow i spent weeks in high school and uni on this shit and didnt understand absolute shit. And in 20 minutes you just told me everything I didnt know good enough

[@thuanvo9283]

Thank you, Errichto!!!

[@franciscneculau3128]

This content is gold ! Thank you !

[@mdshakilhossen2755]

I am a big fan of you from Bangladesh.please upload some video on graph theory.

[@sagarchandradas6326]

We need more dp lectures which is needed to competitive programming.

[@email4pranav]

Amazing tutorial makes dp look so easy

[@lukas041293]

Sorry if i missunderstood something but i have a question: Always you can solve a dp problem in both (iterative and recursive) or might be problems that is possible only recursively or iterative?

[@BlockDesignz]

Lucas Guerrero Any recursive problem can be solved iteratively.

[@diegonayalazo]

Thanks for sharing young Master

[@SuperArjun11]

Fantastic as always tbh. How many problems do you think you're going to go over?

[@Errichto]

I have no idea, to be honest.

[@luasantilli5814]

My notes, feel free to iterate if I got something wrong or if there is something that should also be here. Usually, when a recursive/naive solution repeats some form of computation multiple times, it is smarter to save and reuse that computation Most of DP problems belong to one of these 3 types (counting, optimization, confirmation) For counting, think of combinatorics first For optimization and confirmation think of greedy first There are two approaches to dynamic programming: iteration and recursion Iteration is running time is faster, easier to understand the complexity, has shorter code, and more advanced techniques Recursion is easier to apply, could have fewer states, and the order does not matter. Just do the computation and add memoization Most people in competitive programming do the iterative approach because of the faster running times and availability of more advanced techniques [MINE] Dynamic programming appears to trade space for faster running times Implementation of Fibonacci Dynamic programming is not necessary for factorial. Since it has a linear structure. The staircase problem has deep structural similarities to the Fibonacci Minimum path sum problem explanation It is useful to think of all of the relevant information at each position. What do you need to remember at each position? Think about what element would be best to start the array with. In minimum problems, it could be infinity

[@algorithm808]

Don't forget : What is important so far ?

[@amanrubey]

ok i'm at a certain position now what do next? pls help me with this. i'm lost here

[@jimmorrisshen]

Best DP video ever. Thanks.

[@davidakoji3696]

Errichto 🗣🗣.....thanks.

[@barakode414]

Thank you Kamil, you are the best!!

[@daved1113]

Fantastic series. Thank you.

[@jayagrawal3468]

really good!! Add playlist for other topics also

[@DHRUVNARAYANSINGH]

Thanks for sharing awesome DP tutorial.

[@JohnWangCH]

Thank you for sharing this. It is really helpful.

[@youveron]

0:5:46 imho should be N+1 to include the last index as well

[@jiachengcheung5447]

You lectures are amazing

[@ritamchakraborty1390]

Please create a series on graphs and graphing algorithms

[@anuranjankumar3989]

Thanks for the playback speed suggestion, but i like 1.75x😉

[@sarveshdubey9347]

Amazing just amazing

[@GospodinStanoje]

In the last problem can someone explain to me why wouln't we just consider doing everything backwards greedy? If we are allowed to move only right and down, can't get move from the destination [row][column] to the start but allowed to move LEFT and UP instead using greedy algorithm. Why wouldn't that be a good way?

[@adityagupta5713]

Consider: 1 1 1 1 1 1 9 2 1 9 1 3 Your algorithm would move from 3 to 1 (left) but then would be forced to pick a 9, whereas a dp solution would correctly pick the 1-1-1-1-2-3 solution. You could I guess also implement a dp solution backwards, kind of like you described, but this is probably harder to implement and therefore unnecessary.