Dynamic Programming lecture #1 - Fibonacci, iteration vs recursion

First of several lectures about Dynamic Programming. It's a huge topic in algorithms, allowing us to speed exponential solutions to polynomial time. I will go through three problems: Fibonacci, Staircase and Min-Path Grid (links to Leetcode in the pinned comment). And you'll learn which method is better: iteration or maybe recursion with memoization. Watch this lecture if you practice for competitive programming or for coding interviews. Consider turning captions on and setting the speed to x1.25.

Please give me suggestions about the format of a lecture or about topics for future lectures.

I’m Kamil Dębowski, better known as Errichto. I compete in and organize programming competitions. I make educational streams on Youtube and Twitch. I'm a finalist of ACM-ICPC, Topcoder Open, Facebook Hacker Cup and Google Code Jam. I got a second place in Google Code Jam 2018. I am/was nutella in Codeforces and target in Topcoder.

Watch me if you want to practice for coding interviews, competitive programming or just algorithms in general. I share my thought process, explain everything, and mention similar problems and techniques/algorithms.

[lijiayi]

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

[pranavgawade]

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!

[alexneagu]

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.

[praveen]

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

[vladimirmakushkin]

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!

[MrLuke]

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

[UnicycleSoul]

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

[vedantsharma]

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.

[valdius]

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 ;)

[jdiaz]

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

[alexcipriani]

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

[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 <3

[victorariasvanegas]

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.

[samarthgupta]

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) <= K ] and Sum of values on path P is minimum.

Maybe you can give some insight/hints. Thanks.

[CrystalSergeant]

pure gold. looking forward for next video

[dumdumbringgumgum]

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

[SanjeevSingh-lgsb]

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.

[cactusbee]

@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]

[CS-lkym]

hey errichto! These videos are awesome and best <3. Please keep making more of these :)