Dynamic Programming Explained (Practical Examples)

[@PrabhuKiranKonda]

Tim, why don't you make a course on Data Structures and Algorithms? Like a complete Bootcamp. It would be really helpful to many people out there..

[@audic2350]

I agree, we won't say no to data structures and algorithms videos :)

[@jhonsuper7065]

Tim, I really appreciate your High Quality video, and honestly I am so happy to see that your almost at 1 million subs. You really inspire me to code, and you are a major motivation to me. Thanks so much.

[@Vancha112]

@♜ Pinned by Tech With Tim 100% genuine T.I.M.

[@kevinmutinda8429]

For the Minimum Sum Subarray - Optimal Solutions; change the value of `min_sum_using_last_element min_sum_using_last_element` to `float("inf").

[@timmyx97]

i = 0 stored1 = 0 stored2 = 1 n = 20 while i < n - 1: stored1 , stored2 = stored2 , stored1 + stored2 i += 1 is this O(n) as well ?

[@not_vinkami]

The fibonacci function memoization is quite neat. However as a math programmer I've to say that this solution is suboptimal. The true optimal solution is in fact even faster def fib(n): gr = (1 + math.sqrt(5)) / 2 return (gr ** n - (1 - gr) ** n) / (2 * gr - 1)

[@melihozkocacik]

@8:02 You can use the cache decorator from functools instead of using your own cache.

[@ag88301]

I was looking for this comment...

[@kokop1107]

Finally a tutorial that is making sense! Most explainations are spoon bad, but of course this great quality is absolutely to be expected from one of my favourite tech channels!

[@francisTriesEverything]

def minSum(numbers: list) -> (int): minsum, minsum_using_elt = float('inf'), float('inf) for i in range(len(numbers)): minsum_using_elt = min(numbers[i], minsum_using_elt + numbers[i]) minsum = min(minsum_using_elt, minsum) return minsum

[@MishaSv]

This is one of the clearest explanations of dynamic programming! It really helps to understand what is happening in those complicated coding questions. I've been watching TWT since the time the channel had 200k subs, and it is what inspired me to start my own channel with Python programming tutorials! 1M subscribers is coming soon Tim!

[@ppbroAI]

Bro, awesome explanation and the clarification that is not possible to use this with every problem is the thing most begginers need. First you need to have a specific mindset to try this.

[@gokulmahajan1713]

Perfect, as a beginner it's difficult to get a feel of what exactly DP is, you have explained it perfectly into your min subarray sum example. Other channels directly jump on usual solutions like writing recursive solutions then adding memoization etc, but failed to explain how O(n2) converted into O(n) and how DP is actually involved in it.

[@liamwelsh5565]

Off topic but I find it interesting that you write your numbers from bottom to top.

[@StefanReich]

16:06 The complexity is O(n^3), not O(n^2) (you forgot to factor in the call to the sum function). Easy to optimize to O(n^2) of course, but I thought I'd point it out for correctness sake and to look really smart (heh)

[@Phiz787]

Excellent lesson! I was definitely able to shift my thinking during your examples, and as you were performing the human-iterating solution to the minimum sum problem I was designing the algorithm in my head. In the end, the code writes itself since the method is so clear. Thanks!

[@diconicabastion5790]

Your second Fib is overly complex and stores more than you need. 3 variables and a for loop is all that is needed. You don't need to store all the solution. You make the same mistake on the one after it as well. You only need to store the last solution, the min_sum, That two values are all you need to compare against the array.

[@martinemanuel8239]

Interesting observation, but I think Tim uses this examples for DP proposes, not only to optimize space or things like that

[@codeyourmood8553]

if anyone don't know the minimum sub array algorithm that is used in this video is kadane's algorithm

[@gidartsproduction5439]

I never knew how to solve programming problems and thanks to Tim, his explanation is clear and I now try at least some. For this kinda video, I appreciate a lot sir... thanks for this high quality information.

[@alimihakeem841]

Thanks Tim. I love the detailed explanation. Could you help make video on data structure and Algorithm

[@AndreasToth]

After having watched this I learned that I already use dynamic programming without knowing that this is a recognised methodology with a name 😊

[@Daedroh]

@ 24:25 it is super clear. Thank you

[@No-uu7wm]

The Fibonacci function can be further optimised with DP if you use an array instead of a dict, generating successive values by adding the last 2 elements, just need to store an extra pointer to the tail

[@virtualizer7451]

The time complexity at 16:07 should be O(N^3). You forgot to include O(N) coming from sum of the list

[@gtALIEN]

@♜ Pinned by Tech With Tim bruh

[@eduardoignacioroblessosa6349]

Crystal clear explanation , thank you!

[@AndreasToth]

I would have tested if n is NOT in the cache and, if not, then calculate and add the key-pair to the dictionary, i.e., cache, and then followed this with a common line that returns the value of the key at cache[n] (i.e., executed in either case n was or wasn't originally found). Coding it this way means no code is repeated. A way to then optimise this is to eliminate the common lookup that isn't necessary following the calculation of the value at n by assigning the value to a variable before storing it in the cache, and then return that value directly.

[@chengao6404]

this video is extremely helpful and inspired by dynamic programming, I appreciate the effort you made!

[@qaiserali6773]

Solve more problems on dynamic programming by continuing this series

[@benx5781]

this is so awesome you simplified the dynamic programming solution much easier i love it!

[@pravachanpatra4012]

Tim can you make DJANGO projects?

[@ripfinity1009]

Great video Tim. A quick question. The final code has some redundant bits, right? As I see it min_sum_using_last_element does not need to exist, instead you can just initialize current_min as array[0], use that in the new current_min calculation and delete the redundant line where you set min_sum_using_last_element = current_min. I know this is an example code but I really got fixed on this and wanted to point it out.

[@macklemo5968]

You're a hell of a teacher fr :)

[@danholm99]

nice explanation. Thank you. I have one little thing....You are using af function called min twice...does that not effect O(n) ? I mean it must sort the array twice.?

[@neumanngregor]

13:49 There is s small mistake, cache[0] = 0 and cache[1]=1, not 1 and 1.

[@KDSBestGameDev]

When you explain the 22:24 you explain that you include the previous element, because -5 is less then six. That's actually not the reason you include it. If the Value is -3 and the previous value is -1, it is not less, but still would lower the value of the result. You eplain it in more detail and better for other parts of the solution. Great video all in all thank you :).

[@Vikasptl07]

Thank you for simple and clear explanation!!!

[@mehdismaeili3743]

Hi,you are very good teacher.thank you.

[@universecode1101]

I appreciate man 👍🏻 practical examples are ✅

[@michelchaghoury870]

@Tech With Tim, great video learned a lot. please can you make of these vids they are really helpful

[@ikhairi83]

Tim, that's really good explanation.

[@nefwaenre]

Yes! So i still remember my school time's fibonacci programming and using dp (in BlueJ) to solve this! That was 14 years ago!! :D If only we had caching back then.

[@shaharsarlk]

Hi, great video. In 15:38 isn't there is another solution as the whole array?

[@AndreasToth]

In your dynamic minimum sum example, you create a variable that's meant to store the minimum sum then forget to update it in your walk-through, well, you did so at least when you got to index 3. P.S. Ah, you end up correcting yourself! 👍

[@nikolaoslibero]

Why do so many people trying to explain dynamic programming use the Fibonacci sequence? It is not an example of an algorithm that benefits from dynamic programming. f(n-2) = f((n-1)-1), We would never need to do it twice as we could could just solve for n, so solving twice was incorrect even before applying dynamic programming. The latter minimum sum subarray problem was great!

[@RahulChauhanart]

Here is my solution for min sum subarray without DP in O(n) def min_sum_subarr(arr): if not arr: return 0 minimum_sum = float('inf') current_sum = 0 for elem in arr: current_sum += elem if current_sum < minimum_sum: minimum_sum = current_sum if minimum_sum > elem: minimum_sum = elem current_sum = elem return minimum_sum

[@bernhardschmidt9844]

That's effectively the DP solution, though. The only real difference between your code and the one from the video is that you don't needlessly keep track of the best solution including each previous element (min_sum_using_element) and instead only that of the last one (current_sum). You do the comparisons a bit differently as well, but they end up doing the same thing as the min calls in the video

[@agustinzavala7755]

Great video, thanks 👍

[@meg33333]

Good explanation Can you also make ML website or app project in 2 or 3 day like brain MRI image detection for Alzheimer disease .

[@11yoyomama]

Cool video and well explained. This is a nitpick and I’m sure you know this and just didn’t want to distract from the point of the video but you shouldn’t pass empty dictionary (or list) as kwargs in Python

[@tubero911]

I think you mean do not use mutable default arguments.

[@11yoyomama]

@@tubero911 yep that’s… what I said?

[@kailashks901]

What is the alternative then?

[@11yoyomama]

@@kailashks901 typically you would use *None* as your default argument then check inside the function with something like “if x is None: x={}”

[@kailashks901]

@@11yoyomama Oh I see. Thank you. Will keep this in mind.

[@Rehanshaikh-uy4vy]

Your videos Inspire

[@supunsankalpa5084]

super video. thnks

[@dinohunter7176]

Hi Tim, I like how you explain solving methods. If possible can you provide pseudocode instead of js code? Some are not familiar with all js syntax shown, but will eventually understand the pseudocode. Thanks.

[@rudyNok]

It's python, not js. And you can't ask Tim to meet your beginner requirements when he's explaining more advanced programming topics. Just go and learn the basics, like everyone else did, is really simple :)

[@cakep4271]

Sweet vid dude! You got them teaching skills much much better than most 👍👍👍👍

[@karma_senpai]

sometimes everybody get bored when doing these favourite thing. I have a question for you tim or anyone else do you get bored when learning programming in your life.

[@cozyrain410]

memoization and tabulation??

[@MoughithROUIS]

Can you make a digital and an analog clock using pygame (tutorial)

[@babitabarman2582]

Hi I am from India 13 years I am able to make colon game in pygame what next language I should learn plese tell

[@enos5192]

It's not about languages, it's about design patterns.

[@convolutionalnn2582]

Master python....Choose the field in which you wanna specialized...For example ,If Machine Learning ,then python is good no new language is need...If it is Android development, then dart ,Kotlin and Java are best

[@babitabarman2582]

@@convolutionalnn2582 best is master python 🤗

[@convolutionalnn2582]

@@babitabarman2582 You could already made a game...You could study more than programming language....I prefer you to choose specific field...You will Master language by implementing the field you choose

[@amirmustafakhan7773]

@@convolutionalnn2582 Artificial Intelligence or Data Science

[@Bunnokazooie]

your cache is secretly a global variable due to mutation and default arguments in python. So it works, but only because youre using some weird corners ot the the language. By accident.

[@bernhardschmidt9844]

In case anyone is interested, the more elegant/pythonic way of doing the memorization would be to just add the @cache decorator from functools to the naive solution

[@Kennethlumor]

Sir please and please help me. I developed E-learning management systems where I want the admin sqlite3 database (user_loader(UserMixin) should be different from the students own how do I go about it. Sir please help 😢 because the project is my final year project that I will be submitting ending of this month

[@AndreasToth]

You confuse things when you say the previous element yet mean the previous minimum sum of the previous element. Things don't get better when, in some cases, you then highlight the previous element instead of the previous minimum sum of that index position.

[@Lunolux]

great video

[@xskiinzy7542]

Hi im a new subscriber ive seen one of your videos of solving this code issue and was wondering if u can assist me with it which would be appreciated p.s im a noob at coding

[@pravachanpatra4012]

10:54

[@AndreasToth]

I really wish that you had reused the same array for the non-dynamic and dynamic version of the minimum sum problem especially for people who attempted to solve the problem using the initial array. Sorry, but your choice of changing the array for the same problem but solved differently was counterproductive.

[@lenickramone]

awesome

[@aniket3935]

I need a laptop to start coding stuff. So...... If you have one please give me

[@dynamics9000]

If you are not making money while sleeping, then you are working for others till end of your life ! Warren Buffett ! an awesome channel and Subbed ! a fellow creator ^^

[@logananderon9693]

Brain hurty

[@parultandon8566]

🇮🇳

[@parultandon8566]

@♜ Pinned by Tech With Tim Done. My phone's notification panel is waiting for the next Tech with Tim video.

[@joepike1972]

Here is my implementation of these in Forth using SwiftForth and Win32Forth. : FIBSTEP ( n1 n2 -- n2 n3) DUP ROT + ; \ Adds two numbers and leaves second number and sum : FIB ( n1 -- n2) DUP 2 < IF . ELSE 0 1 ROT 1 DO FIBSTEP LOOP . DROP THEN ; \ If n1 < 2 return n1 else loop FIBSTEP n1 times and returns n3 from FIBSTEP : SMIN ( n1 n2 -- n2 n3) SWAP DUP ROT + MIN ; \ Returns min of n2 and the sum of n1 and n2 : CMIN ( n1 n2 n3 -- n4 n5) ROT ROT SMIN DUP ROT MIN ; \ Returns SMIN of n1 n2 and the min of SMIN n3 : TMIN ( n1 n2 ... -- n) DEPTH 1 - >R .S SMIN DUP R> 1 DO CMIN LOOP .S MIN ; \ Finds min of CMIN over indefinite array

[@CarlosGrillet-fn1lk]

using dp is way more faster, look how much is the difference on my computer n= 40 102334155 fib with dp took: 0.001s 102334155 fib with no dp took: 36.160s

[@ShobiPPpro]

does anybody have a leetcode/hackerrank link to the problem?

[@mrCetus]

I never knew how to solve programming problems and thanks to Tim, his explanation is clear and I now try at least some. For this kinda video, I appreciate a lot sir... thanks for this high quality information.