Dynamic Programming Explained (Practical Examples)
ฝัง
- เผยแพร่เมื่อ 3 ส.ค. 2024
- Have you ever wondered what Dynamic Programming is? Well in this video I am going to go into the definition and the theory of Dynamic Programming! I am also going to talk to you about how to classify certain problems to know if you can use Dynamic Programming for them, and then I will show you some examples and how to optimize the solutions for them! Thanks for watching and I hope you enjoy!
💻 ProgrammingExpert is the best platform to learn how to code and become a software engineer as fast as possible! Check it out here: programmingexpert.io/tim and use code "tim" for a discount!
📄 Resources 📄
BigO Notation: • Big O Notation & Time ...
⭐️ Timestamps ⭐️
00:00 | Overview
01:00 | Dynamic Programming Definition
02:37 | Fibonacci Sequence - Problem
05:03 | Fibonacci Sequence - Trivial Solution
08:02 | Fibonacci Sequence - Optimal Solution
14:39 | Minimum Sum Subarray - Problem
15:57 | Minimum Sum Subarray - Trivial Solution
17:56 | Minimum Sum Subarray - Optimal Solutions
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
👕 Merchandise: teespring.com/stores/tech-wit...
📸 Instagram: / tech_with_tim
📱 Twitter: / techwithtimm
⭐ Discord: / discord
📝 LinkedIn: / tim-ruscica-82631b179
🌎 Website: techwithtim.net
📂 GitHub: github.com/techwithtim
🔊 Podcast: anchor.fm/tech-with-tim
🎬 My TH-cam Gear: www.techwithtim.net/gear/
💵 One-Time Donations: www.paypal.com/donate?hosted_...
💰 Patreon: / techwithtim
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
⭐️ Tags ⭐️
-Tech With Tim
-Dynamic Programming
-What is Dynamic Programming
-Dynamic Programming Explained
-Examples of Dynamic Programming
⭐️ Hashtags ⭐️
#TechWithTim #DynamicProgramming
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..
I agree, we won't say no to data structures and algorithms videos :)
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.
@♜ Pinned by Tech With Tim 100% genuine T.I.M.
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!
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.
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!
this is so awesome you simplified the dynamic programming solution much easier i love it!
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.
For the Minimum Sum Subarray - Optimal Solutions; change the value of `min_sum_using_last_element
min_sum_using_last_element` to `float("inf").
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!
Thank you for simple and clear explanation!!!
Off topic but I find it interesting that you write your numbers from bottom to top.
this video is extremely helpful and inspired by dynamic programming, I appreciate the effort you made!
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)
I appreciate man 👍🏻 practical examples are ✅
@Tech With Tim, great video learned a lot. please can you make of these vids they are really helpful
@8:02 You can use the cache decorator from functools instead of using your own cache.
I was looking for this comment...
Crystal clear explanation , thank you!
After having watched this I learned that I already use dynamic programming without knowing that this is a recognised methodology with a name 😊
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)
Thanks Tim. I love the detailed explanation. Could you help make video on data structure and Algorithm
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.
Interesting observation, but I think Tim uses this examples for DP proposes, not only to optimize space or things like that
Hi,you are very good teacher.thank you.
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 ?
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.
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
You're a hell of a teacher fr :)
The time complexity at 16:07 should be O(N^3). You forgot to include O(N) coming from sum of the list
@♜ Pinned by Tech With Tim bruh
Great video, thanks 👍
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.
@ 24:25 it is super clear. Thank you
Solve more problems on dynamic programming by continuing this series
Your videos Inspire
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.
if anyone don't know the minimum sub array algorithm that is used in this video is kadane's algorithm
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
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.
super video. thnks
Hi, great video.
In 15:38 isn't there is another solution as the whole array?
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.
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 :)
Tim can you make DJANGO projects?
great video
13:49 There is s small mistake, cache[0] = 0 and cache[1]=1, not 1 and 1.
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 :).
Sweet vid dude! You got them teaching skills much much better than most 👍👍👍👍
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.?
Tim, that's really good explanation.
Good explanation
Can you also make ML website or app project in 2 or 3 day like brain MRI image detection for Alzheimer disease .
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
I think you mean do not use mutable default arguments.
@@tubero911 yep that’s… what I said?
What is the alternative then?
@@kailashks901 typically you would use *None* as your default argument then check inside the function with something like “if x is None: x={}”
@@11yoyomama Oh I see. Thank you. Will keep this in mind.
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.
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! 👍
Can you make a digital and an analog clock using pygame (tutorial)
Optimization is simply finding the shortest path? tats y am asking the question here.
memoization and tabulation??
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
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.
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
awesome
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!
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
Hi I am from India 13 years I am able to make colon game in pygame what next language I should learn plese tell
It's not about languages, it's about design patterns.
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
@@convolutionalnn2582 best is master python 🤗
@@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
@@convolutionalnn2582 Artificial Intelligence or Data Science
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
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
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.
10:54
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.
I need a laptop to start coding stuff. So...... If you have one please give me
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 ^^
Brain hurty
🇮🇳
@♜ Pinned by Tech With Tim Done. My phone's notification panel is waiting for the next Tech with Tim video.
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
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
does anybody have a leetcode/hackerrank link to the problem?
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.