Dynamic Programming 1D - Full Course - Python

[@NeetCode]

🚀 neetcode.io - Get access to every current and future course I ever create. Spreadsheet from the video: docs.google.com/spreadsheets/d/1A2PaQKcdwO_lwxz9bAnxXnIQayCouZP6d-ENrBz_NXc/edit?usp=sharing

[@hakeemdhayal8433]

Hi Mr NeetCode dude, I just wanted to ask, do you have tier pricing that changes based on the country? For example, there are developing countries in Africa that generally tend to have a lower pricing since the $ is extremely high to the ZAR - South African Rand. There are other countries as well that would struggle. Do you intend on having a way to assist us too? I'm asking because you're having a launch sale and perhaps by the time you even get a chance to consider different tier pricing based on different countries it may be too late :( Do know however, I'm extremely grateful for the existence of NeetCode and everything that you've done!

[@mybuddy11]

Dear Neetcode, Could you please publish a video full course on graph theory

[@sherazdotnet]

I'd like to share a few points. With DP, one of the main challenge is how do you recognize a problem is indeed a DP problem. It can be misleading at times that a given problem is indeed a DP problem. Therefore, I'd say that this course and more upcoming DP parts that you might be posting, would be great if you start each question with pure analysis of why this problem is a DP problem to begin with. Taking a view on the question as if it has never been seen and then you apply contain ideas to identify if its a DP problem or not. The reason I'm bringing this point is because it just so happened that one of my friend shared his experience with me that he had a few years ago where during interview, he thought the problem is a DP and after 25 mins in the interview, he realized that's its not but he had waisted essentially all the critical time. Long story short, would be great that for every question, would be great to talk about what attributes of such problem made it obvious that its a DP problem.

[@emmanuelu]

Facts. for me personally almost every question i do im always trying to look for a dp solution but i dont really know if it is a dp problem

[@davesmith5043]

I get your point and I agree but I believe it's one of those things that you have to build an intuition for, in other words, it comes with practice.

[@mrmotomoto]

In an algorithms class one first learns about greedy algorithms, then memoization before moving into DP. I think this helps build an intuition. So anyone looking to gain intuition about when DP is applicable may benefit from reading up on those concepts first, especially memoization. That said, the first example of the fibonacci sequence is a good start. Think of times where work has to be repeated because future calculations require the work of previous steps, as in the fibonacci sequence. With memoization, instead of re-calculating every step, we can save the results at each step and recall the solution in future function calls to speed up the time needed.

[@ktm00072]

Take this as how to recognise the problem is a DP: 1. With pen & paper, do the problem have sub-problems? 2. Does the sub-problems return similar value or in a pattern that will be used for next iteration(sub-problem)? If it is, then try to solve this way: 1. you can follow tabulation(array to store data) or memoisation(hashSet or hashMap). 2. Sometimes the problem may not ask for the dp array or dp hash, then you may use two variables(think these as pointers that may need to update at each iteration). At the end return the value.

[@RandomShowerThoughts]

Good question, another one that I have is how do we come to understand that there is a binary algorithm at place? Either we take the current value or we do not? It would appear that we could just loop through all possible options (except the current one), which would still work, but be slower and get a TLE on leetcode

[@temik26]

You're doing amazing work for all who wants to be good at algorithms and pass interviews. Mad respect!

[@mohammedumarfarhan9900]

Thanks a lot brother. May God bless you abundantly

[@lazzalicious6220]

Most loving KZbin commenter

[@reebaqureshi9079]

I've been watching your videos so much through my interview preparations that your voice sounds like a mother's lullaby to me at this point.

[@arno.claude]

Thanks!

[@peekaboo6026]

Ohhh neetcode only if I could express how much I owe you for improving my problem solving skills

[@zizzlindawg1847]

This is amazing, thanks for all the work you do.

[@house0795]

I agree, climbing stairs was indeed explained top notch.

[@alexgabriel5877]

great stuff! hope for other topics covered the same way!

[@jonathanpangilinanjr.9905]

Thank you very much for this video. I finally solved my very own medium dp lc after watching a quarter of your video. I'm gonna finish this and hopefully, I can stand on my own feet after.

[@bubblesort8760]

The best timing. İ was in need of this. Thank you so much Sir.

[@b9944236]

I paid for the lifetime membership yesterday, but this super long and helpful video is just for free. So, goodbye my money, I have to support this cool guy indeed.

[@CyberMew]

that's a great pic of Son Ye-jin!

[@Casanovajosh]

Well, this does not include the 20 mins 1D DP course in his pro member content. Your money is still worth it.

[@undergrad4980]

Dear Neetcode, thank you for uploading this. I have been following your content for quite some time and I really appreciate the effort you have put into creating content for DSA. However, I would really appreciate it if you could highlight the core in-depth reason for why such DP patterns exist, and how to identify them. So a template, instead of solutions.

[@sherazdotnet]

DP is used when you have n ways to do something. Here that n is the number of steps you can take. The question can be changed to say you can can take 1 or 2 or 3 steps. Now if you give 20 stairs, you have 3 ways to get there. As you can see there is no straight forward answer. This is where DP comes in the picture. DP allows you to break the problem down into a very very small sub problem. Once you solve small sub problem then next problem builds on top of it. So instead of solving to 20 steps, solve it for smaller number. What's the smallest number you can solve it for???? 0. Also in dp questions where we have to count n ways, I find it much better approach to go backwards. Instead of finding ways to get to 20, find ways to get to 0. for 3 steps where you are allowed to take 1or 2 steps, it'd look like 3 2/ \1 1 2 2/ \1 2/ \ 1 -1 0 0 1 2 / \1 -1 0 Anytime you see 0, you have a positive case meaning that path will yield correct result. If value goes < 0, it means it won't work. So the code will look like public int GetCount(int totalSteps) { if(totalSteps == 0) return 1; if(totalSteps < 0) return 0; return GetCount(totalSteps-2) + GetCount(totalSteps-1); } Then you add memoization to optimize the time but you get the idea. Its an amazing concept but once you get a hang of it, you'd feel most satisfied solving these questions.

[@cupofjava5480]

@@sherazdotnet you're awesome

[@malikau917]

@@sherazdotnet thanks bro

[@xzex2609]

Climbing Stairs can be written in just three lines(instead of five), in python for swapping two variables you don't need a Temp variable, you can use a, b = b, a or ( one, two = one + two, one ) class Solution: def climbStairs(self, n: int) -> int: one, two = 1, 1 for i in range(n-1): one, two = one + two, one return one

[@longvu7746]

For anyone reading this, reason this works is because in python the expressions on the right side of the = sign are evaluated first, therefore one + two and one are calculated based on original values of one and two. Then it assigns the results to one and two on the left side

[@bullymaguire2335]

@@longvu7746 goated

[@rohithboppey3205]

I'm not sure who needs this, but I guess we can use the similar format for all 1D problems- class Solution { public: int solve(vector& ways, int n, int start){ if(start >= n){ // no way to reach the end return 0; } if(ways[start] != -1){ // already calculated return ways[start]; } // not cal // need to cal // it always depends on the next problem return ways[start] = solve(ways, n, start + 1) + solve(ways, n, start + 2); } int climbStairs(int n) { // using the concept of DP vector ways(n + 1, -1); if(n < 2){ return 1; } ways[n] = 0; ways[n-1] = 1; ways[n-2] = 2; // ways means number of ways we can reach the end // if the start position is i solve(ways, n, 0); return ways[0]; } };

[@curosity276]

I really appreciate your work, your explanation really works

[@eddiej204]

Bro, this is gold.

[@petervan7372]

13:20, at the last step 5, how many ways to land on the same step land on itself, why 1?

[@aniquatabassum5428]

In the climbing stairs problem, why is the value for the base case 1? If we are at the base case, then there are 0 ways to reach the base case right….? I realise if we initialise the base case to zero then the code won’t work. I just want to understand what other reason there is for the base case to be one.

[@SkillR1]

The original problem is about routes - how many routes can you take. from 5 to 5 you can take 1 route from 2 to 5 you can take the route that will lead you to 3, or the route that will lead you to 4

[@willreed9433]

@@SkillR1 ik both these comments are super old but I think OP is saying: from 5 to 5 you can take 0 routes, since moving at all would lead you away from 5. it is counter-intuitive when thinking in literal terms. So the route of "not moving at all" is considered 1 route, the only possible route, when already standing on the final step (to make it logical in a real life scenario).

[@Vishal_84_k]

Waiting for this ,best explaination ever 💥💥

[@krishnamohantiwari1140]

Amazing!! Waiting for 2D DP :)

[@Hossein118]

Absolutely love your content. It’s so neet and easy to follow for the layman. Do you have a Rumble channel as well?

[@iworeushankaonce]

I can't believe this is free. Thank you NeetCode!

[@ruiqiyin3847]

This is what I'm looking for! Thank you!

[@vikasjha1064]

Best playlist to learn DP. Thanks mate

[@utkarshdewan8736]

Oh my man this was so needed thankyou so much sir ❤️

[@jessanraj9086]

I Really appreciate these efforts you are taking man🔥

[@rahuldey1182]

Neetcode is the Hero we dont deserve but the hero we needed. He is the Dark Knight of LeetCode.

[@sharksinvestment9864]

Thanks neetcode

[@khirabdhitanaya8931]

You. Are. Absolutely. Amazing!!!!

[@ujjawalpanchal]

@neetcode Props on the great video! Are palindromic substrings and longest palindromic substrings relevant to DP? If not, why are they in this compilation?

[@svkrtrolls7438]

great content

[@RohitRavula]

Thanks a lot, We need more such full course vedios on each module, It really helps

[@sherazdotnet]

Here is my solution using Recursion + Memoization. Code is written in c# public int CountSteps(int totalSteps, Dictionary memo) { if(totalSteps ==0) { return 1; } if(totalSteps < 0) { return 0; } if(memo.ContainsKey(totalSteps)) { return memo[totalSteps]; } var usingOneStep = CountSteps(totalSteps-1, memo); var usingTwoSteps = CountSteps(totalSteps-2, memo); memo[totalSteps] = usingOneStep + usingTwoSteps; return memo[totalSteps]; }

[@tofahub]

Watching this in the weekend. I can't be happier

[@sophiophile]

2:08:59 why is the third value in the min necessary (just n). cur_max can never be less than 1. If cur_max is 1, its the same as n, if its larger, it's bigger than n.

[@amandubey5287]

You did it finaly, God Damn, you have no idea what great help you just did, damn bruh you are God sent

[@amospan14]

Dude this is amazing material! Thank you so much for the education and your teachings! When I get a job, Ima have to take you out for lunch! Truly appreciate your work buddy =)

[@varadiganesh7389]

Great stuff... Learnt a lot sir

[@mikkiverma9545]

Thanks neetcode eagerly waited for this, Hope u will upload this type of content more.

[@AbhishekSingh-vl1dp]

Can't believe he is an Indian 🫡😂

[@dontignore5567]

Only Indian can do this bro

[@DreamosStudio]

Wow, this is amazing tutorial, DP in many case (n*2) -1 or ( n- n,pow(2)) 😀, great work

[@pawanchaturvedi8973]

Oh my God ! Can't thank you enough. Thank you so much for this

[@RajatSoni07]

Very helpfull course, Highly recommended

[@ek_minute_]

Thanks man. Respect from 🇮🇳

[@rustomshroff417]

the two variable approach to solving the decode ways is missing in this video, but really helpful video. Thanks a lot.

[@09TYPER]

Thanks!Could you do live dynamic programming session , so we can learn from your thought process?Btw( for 02:45:45 ) if the input array is [1,4,11,5} dont [1,4] and [5] is even subsets,even if they are not equal to half of sum of the array?

[@akhildeshneni9922]

Thank you neetcode 🙌

[@abhaytiwari5991]

Well done bro👏👏👏👏👏👏

[@the8426]

I love this, Thank you! Can you do the same for dfs and bfs algorithms?

[@harryzachariou1]

Absolute legend for this!

[@madhumithakolkar_]

Brute Forced a super inefficient piece of code :P : def wordBreak(self, s: str, wordDict: List[str]) -> bool: length = len(s) for w in wordDict: if length==0: return True while length>=0 and len(w)

[@347harsha]

Thanks Guru. You are my Dronacharya

[@hazelpham2404]

THANK YOU SO MUCH!

[@saminhasan87]

this video helped me a lot. Thanks

[@sophiophile]

Can we improve the efficiency at 2:24:28 by mutating wordDict into the form where the key is len(word) and the value is a list of all words of that length (no extra space). Then we can check: for key in wordDict: if i+key in dp and dp[i + key] = True: for word in wordDict[key]: #check the word That way, you eliminate the vast majority of building dp.

[@ErenTal]

Hello everyone! I have a question regarding the problem 300 "Longest increasing subsequence". Why didn't we write: LIS = [1] * (len(nums)+1) instead of LIS = [1] * len(nums) For example, in the previous problem "Word Break" we've used the +1. In which cases do we use the +1 when we define dp and in which cases we do not? Thank you

[@pushkarchaubey8300]

you are god for me and thanks for these dp course in python🙂🙂

[@CyberMew]

Is this video a combination of all the previous videos cut together? or is it recut/edited to string together experiences drawn from previous questions?

[@chrisogonas]

So incredible you could put in tonnes of hours into quality work. Thanks for creating this amazing resource.

[@intrepidm8753]

love you dude.... if God is there... God bless you

[@romo119]

For problem "decode ways" Doesn't initializing dp[len(s] = 1 mean that null string can be decoded in 1 way? I understand how this works in code but conceptually I don't see how a null string can be decoded

[@ra90451]

Odd or even length strings does not matter static boolean isPallindrom(String str) { boolean isTrue =false; int l=0; int r =str.length()-1; while(r>l) { System.out.println(str); if (str.charAt(l)==str.charAt(r)) { isTrue=true; }; l++; r--; } return isTrue; }

[@jasmin_bheda]

Love you Neetcode ❤

[@godmodel33t11]

For the first 1D example, why does the fib sequence start from 1 and not 0?

[@mybuddy11]

Dear Neetcode, Could you please publish a video full course on graph theory

[@aloussase]

At 2:09:00 the nasty bug could be avoided using a pure fold instead of mutations

[@qray862]

thank you for the contribution for the human kind.

[@Dishankjindal]

Amazing 👍🏼

[@PROJECTMartin]

At 1:57:00 you're solving Maximum Product Subarray not Longest Increasing Subsequence

[@NeetCode]

thanks, fixed

[@ZhenkarGowdaKP]

This is way simpler for i in range(2, len(nums)): temp = min(nums[i-2] , nums[i-1]) nums[i] = nums[i] + temp return min(nums[-1], nums[-2]) btw I got this idea by seeing ur house robber1 leetcode problem

[@jamesbotwina8744]

That infinite loop while trying to add to the same set you are iterating through was confusing me. Thanks!

[@NareshKumar-vy1bi]

Hey Neetcode, What app and tool you use for teaching?

[@mayursonowal]

You’re doing god’s work

[@MukulDuttshades]

Thank you🫂

[@evergreenyoung1181]

For the last problem, can someone explain why the time complexity is not 2^n? If all the sum is unique, then the size of set should double each time, thus it's 2^n. Why doesn't this happen?

[@piyush1342]

Love you man you are the best

[@henryskalitz9094]

I paid for a course to learn about dynamic programming but I had to come here to actually understand it

[@yaswanthkosuru]

really learning dp from a google employer is a god grace

[@ionguzun3952]

Nice video...can u please do a video about sliding window technique

[@psibarpsi]

Thanks a lot!

[@beyond-convention]

Hi Your whiteboard is amazing. Which tool do you use for whiteboarding

[@infohub3709]

@ 18:53 the code doesn't run well for a higher value of n. I tried with a value of 500,000. It hung.

[@alexanderkuptsov6117]

First of all, a lot of thanks for what you have done, such effort is priceless and let good things happen to you! :) Things I would have done differently: I have just finished watching the first problem, which is Climbing Stairs, and I have to say your approach to explaining it is a bit misleading in its final part. First, you're indexing your array from 0 to 5, but it's dp[0] that contains the number of ways to reach 5. At the same time dp[5] = 1 and that might be confusing because clearly there's more than 1 way to reach 5 from 0 to 5. I do realise that you decided to go backwards but why? Your initial explanation was from 0 to 5. Also, when you show the code, you have no array in there at all. Yes, it's clear that this problem is a plain Fib numbers problem, but for someone who's just started that might be confusing. Anyway, thank you for your effort and don't think of me as someone unthankful - I'm not. I've written all that for those who may struggle trying to understand these things because I've been there multiple times myself.

[@pratikmhatre4815]

Superb explainations

[@shashankvray9042]

MY MAN IS BACK

[@shivangitiwari2485]

your voice is very appealing.

[@Phantom_Blox]

thanks for teaching me how to rob a neighborhood efficiently

[@AnkitKumar-jm3cz]

Really Awesome work . Thank you so much Bro

[@dranzerashi]

in maximum product subarray how does the solution ensure the min max product is from a contigous sub array and not from a non contiguos one

[@ИринаГусев-р9ю]

When I see your video I realize the next 3 hours are gonna be coool

[@alexanderkuptsov6117]

1:01:07 - LeetCode 5 doesn't look like DP, more like two pointers.

[@彭程-u8k]

I have a question for Maximun Product Subarray. What if the array is just [0], your code will output 1 as u set curMax as 1 by default. However, the ans should be 0 right? Maybe I should deal with this case especially?

[@honas908]

how is the palindrome question related to dynamic programming? (Great vids, btw!)

[@ryangoodwin9115]

im confused by what i see and what i hear. you say the for loop will run until it reaches the beginning of the array. but whats written is -3, -1, -1 so to my understand, it starts at index -3, then goes back -1 index every iteration, until it reaches the last index -1?? that makes no sense to me

[@nurhusni]

why is bottom up solution considered the "true" DP solution?

[@ScaryYokai]

Thanks !!!

[@Aryan-wl7mc]

Legend is back 🔥🔥🔥

[@s8x.]

What’s the difference between this and recursion