Dynamic Programming Explained (Practical Examples)

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!

📄 Resources 📄

⭐️ 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

◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️

◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️

⭐️ Tags ⭐️
-Tech With Tim
-Dynamic Programming
-What is Dynamic Programming
-Dynamic Programming Explained
-Examples of Dynamic Programming

⭐️ Hashtags ⭐️
#TechWithTim #DynamicProgramming

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

[jhonsuper]

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.

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

[kokop]

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!

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

[timmyx]

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 ?

[melihozkocacik]

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

[kevinmutinda]

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

[gokulmahajan]

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.

[Phiz]

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!

[liamwelsh]

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

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

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

[alimihakeem]

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

[No-uuwm]

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

[ripfinity]

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.

[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

[chengao]

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

[eduardoignacioroblessosa]

Crystal clear explanation, thank you!

[benx]

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