Mastering Dynamic Programming - How to solve any interview problem (Part 1)

Подписаться 42 тыс.

Просмотров 595 тыс.

50% 1

🎬 Mastering Dynamic Programming: An Introduction 🎬
Are you ready to unravel the secrets of dynamic programming? 🤔 Dive into the world of efficient problem-solving with this comprehensive introduction to dynamic programming. Whether you're a budding programmer or an algorithm aficionado, this video is your gateway to understanding the magic behind DP.
🔑 Key Takeaways:
📌 Demystifying the concept of dynamic programming.
📌 Understanding the core principles behind dynamic programming.
📌 Unleashing the power of recursion and memoization.
📌 Step-by-step breakdown of dynamic programming problem-solving.
Dynamic programming is like a puzzle-solving technique, and this video is your ultimate guide to fitting the pieces together. Get ready to elevate your coding skills and witness the art of optimization in action.
🚀 If you found this video helpful, don't forget to like, share, and subscribe for more tech tutorials!
Checkout part 2: • Mastering Dynamic Prog...
🌐 SiteGround: the hosting solution I like (affiliate link): www.siteground.com/index.htm?...
📖 Introduction to Algorithms, one of the key books about algorithms (affiliate link): www.amazon.com/Introduction-A...
🔗 Connect with me:
Support me on patreon: / techwithnikola
LinkedIn: / nikola-stojiljkovic-67...
Join my discord: / discord
Visit my blog: techwithnikola.com
Follow me on Instagram: / techwithnikola
Follow me on Twitter: / techwithnikola
Timecodes
00:00 - Intro to DP
01:40 - Problem: Fibonacci
04:44 - Memoization
06:22 - Bottom-Up Approach
07:20 - Dependency order of subproblems
07:52 - Problem: Minimum Coins
13:39 - Problem: Coins - How Many Ways
15:22 - Problem: Maze
18:55 - Key Takeaways

Наука

Опубликовано:

9 июн 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 397

@JulenSanAlejoGonzalez 6 месяцев назад

Dynamic programming -> Dont do what is already done

@dave6012 8 месяцев назад

Wow, “recursion + memorization” is the most eloquent way I’ve ever heard it defined. Total crystallizing moment for me, even though I’ve used dynamic programming solutions before.

@TechWithNikola 8 месяцев назад

Thank you for the comment. I'm glad that you've found that reasoning useful :)

@Pseudo___ 7 месяцев назад

How was that not obvious? Given you’ve done it before

@tantalus_complex 7 месяцев назад

@@Pseudo___ What are you expecting them to say? You're just insulting them while showing off your own ignorance about how learning works. Way to be a pointless buzzkill about someone's a-ha moment. Many explanations _don't_ reduce DP to such a simple, concise rule of thumb. So if a learner of DP didn't get lucky enough to benefit from one or more accessible explanations of the subject by educators, then _of course_ they will require time and experience before they'll be able to synthesize such an explanation for themselves. And by far, the most likely time for a simple explanation to finally "click" with any learner is _after_ they have already successfully developed a good _intuition_ for the subject. This person vocalized the joy of that final "click" - which is the glory of education itself. That's just awesome. It certainly does not warrant your unsolicited negativity.

@felipao2134 6 месяцев назад

@@tantalus_complexnice comment

@Vastaway 4 месяца назад

i think the main problem is that recursion is too slow. tabulation combines memoization and greedy very well, and although runs in the same time complexity as recursive + memo solutions, generally take up less time and memory since recursive calls are expensive timewise and in the memory/stack

@divy1211 9 месяцев назад

This has to be one of the best dynamic programming videos out there. Props! Something that I feel could have been mentioned though is that a lot of the times it is also useful to reframe the problem which can make the solution a lot more intuitive as well. Whilst I understand that the point of the last maze problem is to teach DP effectively (it is a good and intuitive example for how a bigger problem can be reframed in terms of sub problems!), a useful observation is that the distance which the rabbit needs to move in an N×M grid is always going to be N-1 rights and M-1 downs. The number of ways is just the total possible arrangements of that many rights and downs, which is given by (N+M-2)! / [(N-1)!(M-1)!]. DP is thus not required for the last problem at all!

@TechWithNikola 9 месяцев назад

Thanks a lot for the comment. Yeah, you are totally right. I was having back-and-forth thoughts about whether I should mention this, and decided against it because my focus was on explaining the intuition behind DP. Similarly, it is possible to compute N-th Fibonacci number in O(log(N)) time complexity and O(1) memory complexity. In retrospect, I should have mentioned both without affecting the explanation of the DP approach. I will remember this for future videos. Thanks again for the feedback. These types of comments are very useful.

@jonaskoelker 8 месяцев назад

I guess the maze example could be made interesting by adding obstacles, such that counting the solutions without enumerating them becomes a lot harder.

@saveriov.p.7725 4 месяца назад

Can you explain where you got this formula?

@arturosalas5399 3 месяца назад

@@saveriov.p.7725 The # of combinations of r unordered elements out of a total of n is; n!/(r! * (n-r)!)

@franepoljak9605 3 часа назад

This is by far the best explanation I've ever seen for dynamic prorgamming!

@patrickstival6179 8 месяцев назад

I think I understand it after rewatching at least 20 times. Putting that knowledge into code is a whole other story. I'm going to search for some more dynamic programming problems

@TechWithNikola 8 месяцев назад

I think that’s normal if you really want to understand it. I think it took me many many attempts as well, and the only way to truly get good at it is to solve many problems.

@DrZainabYassin 6 месяцев назад

Can I ask something

@wbrehaut 6 месяцев назад

@@DrZainabYassinYou don't need permission to ask something. Just go ahead and ask!

@jst8922 5 месяцев назад

Here are some classic dynamic programming problems: part I: Fibonacci Numbers: Problem: Compute the nth Fibonacci number. Dynamic Programming Approach: Use memoization or bottom-up tabulation to store and reuse previously computed Fibonacci numbers. Longest Common Subsequence (LCS): Problem: Given two sequences, find the length of the longest subsequence present in both of them. Dynamic Programming Approach: Build a table to store the lengths of LCS for different subproblems. Longest Increasing Subsequence (LIS): Problem: Given an unsorted array of integers, find the length of the longest increasing subsequence. Dynamic Programming Approach: Build a table to store the lengths of LIS for different subproblems. Knapsack Problem: Problem: Given a set of items, each with a weight and a value, determine the maximum value that can be obtained by selecting a subset of items with a total weight not exceeding a given limit. Dynamic Programming Approach: Create a table to store the maximum value for different subproblems. Coin Change Problem: Problem: Given a set of coin denominations and a total amount, find the number of ways to make the amount using any combination of coins. Dynamic Programming Approach: Build a table to store the number of ways to make change for different subproblems. Edit Distance: Problem: Given two strings, find the minimum number of operations (insertion, deletion, and substitution) required to convert one string into another. Dynamic Programming Approach: Build a table to store the minimum edit distance for different subproblems. Matrix Chain Multiplication: Problem: Given a sequence of matrices, find the most efficient way to multiply them. Dynamic Programming Approach: Build a table to store the minimum number of scalar multiplications needed for different subproblems. Subset Sum: Problem: Given a set of non-negative integers, determine if there is a subset that sums to a given target. Dynamic Programming Approach: Build a table to store whether a subset sum is possible for different subproblems. Rod Cutting Problem: Problem: Given a rod of length n and a table of prices for rod pieces of various lengths, find the maximum value obtainable by cutting the rod and selling the pieces. Dynamic Programming Approach: Build a table to store the maximum value for different subproblems. Maximum Subarray Sum: Problem: Given an array of integers, find the contiguous subarray with the largest sum. Dynamic Programming Approach: Keep track of the maximum subarray sum ending at each position in the array. part II: Palindrome Partitioning: Problem: Given a string, partition it into as many palindromic substrings as possible. Dynamic Programming Approach: Build a table to store the minimum number of cuts needed to partition substrings into palindromes. Word Break Problem: Problem: Given a string and a dictionary of words, determine if the string can be segmented into a space-separated sequence of dictionary words. Dynamic Programming Approach: Build a table to store whether a substring can be segmented using the given dictionary. Longest Palindromic Substring: Problem: Given a string, find the longest palindromic substring. Dynamic Programming Approach: Build a table to store whether substrings are palindromic. Count Distinct Subsequences: Problem: Given a string, count the number of distinct subsequences of it. Dynamic Programming Approach: Build a table to store the count of distinct subsequences for different subproblems. Maximum Sum Increasing Subsequence: Problem: Given an array of integers, find the maximum sum of increasing subsequence. Dynamic Programming Approach: Build a table to store the maximum sum of increasing subsequences for different subproblems. Largest Sum Rectangle in a 2D Matrix: Problem: Given a 2D matrix of integers, find the largest sum rectangle. Dynamic Programming Approach: Reduce the problem to finding the largest sum subarray in each column. Egg Dropping Problem: Problem: You are given k eggs and a building with n floors. Find the minimum number of drops needed to determine the critical floor from which eggs start to break. Dynamic Programming Approach: Build a table to store the minimum number of drops for different subproblems. Counting Paths in a Grid: Problem: Given a grid, find the number of unique paths from the top-left corner to the bottom-right corner. Dynamic Programming Approach: Build a table to store the number of paths for different positions in the grid. Wildcard Pattern Matching: Problem: Given a text and a wildcard pattern, implement wildcard pattern matching with '*' and '?'. Dynamic Programming Approach: Build a table to store whether substrings match for different subproblems. Minimum Cost Path in a Matrix: Problem: Given a 2D matrix with non-negative integers, find the minimum cost path from the top-left corner to the bottom-right corner. Dynamic Programming Approach: Build a table to store the minimum cost for different subproblems. part III: Distinct Paths in a Grid: Problem: Given a grid of m x n, find the number of unique paths from the top-left corner to the bottom-right corner, where movement is allowed only down or to the right. Dynamic Programming Approach: Build a table to store the number of unique paths for different positions in the grid. Count Palindromic Subsequences: Problem: Given a string, count the number of palindromic subsequences. Dynamic Programming Approach: Build a table to store the count of palindromic subsequences for different subproblems. Maximum Length Chain of Pairs: Problem: Given pairs of integers, find the length of the longest chain of pairs such that the second element of the pair is greater than the first element. Dynamic Programming Approach: Sort the pairs and apply a dynamic programming approach to find the longest chain. Longest Bitonic Subsequence: Problem: Given an array of integers, find the length of the longest bitonic subsequence. A bitonic subsequence is one that first increases and then decreases. Dynamic Programming Approach: Build tables to store the length of increasing and decreasing subsequences for different subproblems. Partition Equal Subset Sum: Problem: Given an array of positive integers, determine if it can be partitioned into two subsets with equal sum. Dynamic Programming Approach: Build a table to store whether a subset with a particular sum is possible. Maximum Product Subarray: Problem: Given an array of integers, find the contiguous subarray with the largest product. Dynamic Programming Approach: Keep track of both the maximum and minimum product subarrays at each position. Decode Ways: Problem: A message containing letters from A-Z can be encoded into numbers. Given a string, determine the number of ways it can be decoded. Dynamic Programming Approach: Build a table to store the number of ways to decode substrings for different subproblems. Shortest Common Supersequence: Problem: Given two strings, find the shortest string that has both strings as subsequences. Dynamic Programming Approach: Build a table to store the length of the shortest common supersequence for different subproblems. Maximum Profit in Stock Market: Problem: Given an array representing stock prices on different days, find the maximum profit that can be obtained by buying and selling stocks. Dynamic Programming Approach: Keep track of the minimum stock price and maximum profit at each position.

@ggmaddr 4 месяца назад

Huge respect for your perseverance. Learning complex topics are frustrating, just put hours, be calm and watch everything again

@user-zs2jv2ds4o 6 месяцев назад

All the great performers I have worked with are fuelled by a personal dream.

@levelplusplus 9 месяцев назад

Tech with Nikola = Tequila 🍸🎉

@rachitdang7453 10 дней назад

)Tech with Nikola, more like Tech with Tesla (you know Nikola Tesla).

@pubringjuandelacruz 8 месяцев назад

thank you for creating videos like this. I've been in the industry for a couple of decades now and still learning new things and approaches. more power to you sir. and looking forward to more videos.

@CapeSkill 8 месяцев назад

@@aqfj5zy what are you waffling about, blud.

@rodneymkay 9 месяцев назад

Really cool. Found this channel through the git video and started watching all the other videos. Really enjoying them so far, so thanks for making them

@TechWithNikola 9 месяцев назад

I'm so glad that you're enjoying my videos. Thanks for taking the time to leave a comment.

@miguelrosa6394 3 месяца назад

Dynamic programming is recursion + memoization, thank you so much I will never forget that connection, it made de concept click for me.

@TechWithNikola 3 месяца назад

You’re welcome! Glad you’ve found it useful. That’s the key realization, and interestingly it took me a long time before I started phrasing it like that.

@systemloc 4 месяца назад

This video is epic. The way everything is explained makes it very easy to understand. The audio is super well recorded. The visuals are well done. If that's not enough, he explains the solution in code in both a recursive and not recursive fashion. I don't use recursion much, and I didn't really understand how to switch between recursive and non-recursive, and now I understand that better as a bonus. Instant subscribe. I hope you make lots of videos.

@TechWithNikola 4 месяца назад

Thanks a lot for the comment. I'm very happy when I hear from people that find it useful and informative. I will definitely make lots more videos, and I hope I'll have more time in the future to upload more regularly.

@temurson 8 месяцев назад

Appreciate your video! I'm decent at algorithmic problems, and knew all of the basic dynamic problems you mentioned in this video, but I liked your emphasis on first writing a brute force solution and then optimizing it. I was a bit confused by your choice to always use bottom-up approach, because in my opinion bottom-up can sometimes be difficult to write as it can be hard to determine which states to update first. I've always found the recursive approach more intuitive, but maybe it's just me. Looking forward to part 2! Hope you can help me find some intuition to solve harder DP problems as those are still pretty difficult for me.

@TechWithNikola 8 месяцев назад

Thank you for the comment. Always using bottom-up approach is a personal preference. The main advantage is that it's easier to reuse memory for memoized solutions when we they are not required anymore. For example, to solve fibonacci with DP, we don't have to use the O(N) memory. Instead, we can only store the last two values. This is very easy to do when using the bottom-up approach, but it's not obvious to me how to do it with the recursive one. Hopefully that makes sense. You are right that the recursive approach is more intuitive and I think it's a perfectly fine approach in most cases.

@nikhilsinha2191 5 месяцев назад

same buddy I too found the recursive approach to be more intuitive but generally looping solutions perform better than recursion as recursion uses the concept of stack behind the sence.

@mikmad97 8 месяцев назад

Hey, Nikola! This was a really useful video, as we're currently going through DP on my Master's. It's such a difficult paradigm to get used to, but your video really helped understanding the paradigm, and hopefully it'll help my future self learning the DP paradigm :) Also, any idea when the next part is coming out? :D

@TechWithNikola 8 месяцев назад

Hello Mikkel, I'm glad you've enjoyed it. Indeed, it takes to get used to the paradigm, but it will happen - just keep practicing. I don't have the exact date for part 2, but a possible timeline is in a month or two. Do you have any suggestions on what you'd like to see in part 2?

@DanielTysonM 8 месяцев назад

I would like to know whether DP is restricted to counting and shortest path problems. I would also like to know how one can solve for an optimal order, if that makes sense? 😊

@mikmad97 8 месяцев назад

@@TechWithNikola I noticed you didn't do much recursion here, and I'd like to see Recursion done using the DP paradigm (I noticed another comment saying something along the same lines). Other than that, no, I don't have any specific topics as of now, that I'd like to see. I might post a new comment as my Master's course progress, but for now recursion done by DP is the only thing :)

@igorbeaver4692 8 месяцев назад

Very looking forward to the 2nd part!

@driden1987 8 месяцев назад

I remember solving the knapsack problem in C++ back when I was studying algorithms at the University. I found it so hard at first, but once it clicks it’s awesome

@TechWithNikola 8 месяцев назад

Indeed. I’ve had the same experience long time ago. I think knapsack was one of the first problems I learned about.

@priyankthakkar6597 11 дней назад

Wow.... A great video to start with dynamic programming. It is like brain is forced to think after a long time

@SALOway 6 месяцев назад

I don't know how, but your video came across as timely as ever! I am a student and I was given a recursion problem. It may not have been necessary, but I'm sure glad that I was able to optimize recursion (which is so much slower than the iterative approach that already for the 50th element you have to wait more than 30 seconds, when the iterative approach manages in less than a second)

@TechWithNikola 6 месяцев назад

Thank you for the comment. I’m glad you’ve found it useful and that the timing was perfect! 😀

@birthdates3933 7 месяцев назад

This was extremely useful and is one of the better dynamic programming explanations I've seen.

@TechWithNikola 7 месяцев назад

Thank you. I'm glad you've liked it!

@AusReddit Месяц назад

Fun fact, for the maze problem, you can also solve this with combinatorics. The key to note is that no matter the path, the number of right moves and down moves end up being the exact same. For the 18 x 6 grid example, you'd need to move 17 down, 5 right in total. Therefore, for 22 total moves, we pick 17 spaces for the down moves and leave the remaining for the right moves. C(22, 17) = 26334 This is equivalent to picking 5 spaces for the right moves and leaving the remaining for the down moves. C(22, 5) = 26334

@tkingless 7 месяцев назад

I knew the examples but not knowing what dynamic programming is until watching this nice explanation. It is like connecting broken pieces into a large one. look forwards to next part

@TechWithNikola 7 месяцев назад

Yeah, it's exactly like connecting broken pieces into a large one. I'm glad you've found the video useful :)

@user-bd8tr7cz5p 8 месяцев назад

Hope this channel grows a lot. I'm on mu first steps on coding, but I know it's gold.

@TechWithNikola 8 месяцев назад

Thank you! Consider sharing this channel with your friends. It would help with the growth a lot 😊

@dozieemodi5558 6 месяцев назад

Thanks so much. Will appreciate a part 2. I just subscribed!

@TechWithNikola 6 месяцев назад

Welcome aboard! Next video will be dynamic programming part 2. Apologies for the delay, I've been sick and didn't have enough time to make a new video.

@pet.me102 16 дней назад

Not gonna lie, I have watched a few videos about dynamic programming, but your video is the only one that I love the most and understand because it has examples lol. Keep up the good work bro, I already subscribed.

@zendr0 9 месяцев назад

Great video Nikola. I would love to see more of these in future. Once again, Thank you for this 😊

@TechWithNikola 9 месяцев назад

Thank you 🙂 You’re welcome. Looking forward to hear your thoughts for my future videos.

@user-io4df1vs3b 6 месяцев назад

Be thankful when you don't know something for it gives you the opportunity to learn.

@asj9469 3 месяца назад

I appreciate this content so much. I personally find recursive functions less intuitive and more of a headache because I constantly have to keep track of what I just did. If I lose it? then yea I have to start over. Maybe there's a smarter way to approach them, but I haven't come across any intuitive explanations for the past 3 years I've been into coding. Your bottom-up approach makes so much more sense though. I just love how we are storing the subproblems for later use. It makes accessing previous information very intuitive and less of a headache for me. I can see the pattern there, and I believe I could apply it to other problems too if I could frame them right. Thank you so much!

@TechWithNikola 3 месяца назад

Hey, thank you for the comment. Yeah, recursion can be tricky but it becomes easy over time. I will consider making some videos about recursion, and try to share my thought process. Bottom-up approach is a good way to improve, but be careful as it can’t replace recursion in many non-DP problems.

@justinv3512 3 месяца назад

Whenever a technical concept is being explained by an eastern european accent, you know you just struck gold.

@TechWithNikola 3 месяца назад

😂 thanks!

@UliTroyo 9 месяцев назад

This is SUCH a good video. Thanks so much! I did the minimum coins problem in Nushell to try to get the concept to stick; it was fun.

@TechWithNikola 9 месяцев назад

Thanks a lot. I’m glad you liked it! 😀

@N9TheNoob 9 месяцев назад

what a blessing of a channel, thanks!

@TechWithNikola 9 месяцев назад

You’re welcome!

@user-cs9pt2dw6e 6 месяцев назад

This world, after all our science and sciences, is still a miracle; wonderful, inscrutable, magical and more, to whosoever will think of it.

@shloksuman8164 9 месяцев назад

really crystal clear explanation on dynamic programming! came here after your git video. Subscribed!!

@TechWithNikola 9 месяцев назад

Thanks a lot. I’m very happy to hear that you’ve liked both videos!

@robbybobbyhobbies 9 месяцев назад

Fascinating, looking forward to future dynamic programming videos.

@TechWithNikola 9 месяцев назад

Thanks!

@diegokarabin2912 5 месяцев назад

Please make part 2!! This video was amazing. Helped me to understand the dynamic programming.

@TechWithNikola 5 месяцев назад

Thank you taking the time to comment. I'm glad to hear that you've found it useful. I have just published the part 2: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-rE5h11FwiVw.html Looking forward to hearing what you think about it. I've tried to keep the same style, but I was moving forward quicker this time, and I don't know if that's appropriate - any feedback is welcome.

@rfpixel 9 месяцев назад

Very good explanation! keep it the good work and I love your videos!

@TechWithNikola 9 месяцев назад

Thank you! This means a lot to me.

@ride_like_bat 8 месяцев назад

Thanks, I have recently started learning DP. Your illustrations helped me.

@TechWithNikola 8 месяцев назад

You’re welcome. I’m glad to hear that.

@musicD.looped 7 месяцев назад

great video, very precise , concise and explanatory waiting for more, keep it up!!!

@TechWithNikola 7 месяцев назад

Thank you!

@user-hq3ty2nx4x 6 месяцев назад

Dan took the deep dive down the rabbit hole.

@leeamraa 2 месяца назад

You are a gifted teacher!!! Great video ... please keep doing what you are doing.👍👍👍

@TechWithNikola Месяц назад

Thanks a lot for the kind words. I really hope I’ll get more free time to make videos soon.

@David-zf6ib 9 месяцев назад

Really good explanation. Thank you very much!

@TechWithNikola 9 месяцев назад

Thank you! I'm glad you've enjoyed it.

@tim3.1415 7 месяцев назад

Unbelievably well done video👍👍 you deserve many more subscribers!!

@TechWithNikola 7 месяцев назад

Thanks a lot! Hopefully one day 😀

@narasimhasudhakar2470 3 месяца назад

You hit this to out of the park...plz plz keep teaching...

@TechWithNikola 3 месяца назад

Glad you’ve liked it. I will. Comments like yours always remind me that it’s worth making more videos

@madhavanand756 3 месяца назад

This is masterpiece, we want more content like this.

@TechWithNikola 3 месяца назад

Thanks, glad you've enjoyed it :)

@maheshchoudary8763 9 месяцев назад

Without this video I wouldn't have gotten the power of both recursion and memorization. Thanks

@TechWithNikola 9 месяцев назад

That’s great to hear. You’re welcome!

@gJonii 8 месяцев назад

Memoization you mean?

@anikettiratkar 7 месяцев назад

Great explanation and visuals! I got very high hopes for this channel.

@TechWithNikola 7 месяцев назад

Thank you!

@ronaldmaldis4394 4 месяца назад

I avided to watch like this video throughout the YT til found your video now. thank you buddy . keep up♥

@TechWithNikola 4 месяца назад

You're welcome :) Glad to hear you've enjoyed it.

@ArchonLicht 8 месяцев назад

Very nice and clear video. Thank you!

@TechWithNikola 8 месяцев назад

Thank you!

@harikirankante883 9 месяцев назад

I would love to see more such quality content on YT ❤❤

@TechWithNikola 9 месяцев назад

Thank you for the kind words! ❤️

@Travelophile Месяц назад

best dynamic programming video i have ever seen

@TechWithNikola Месяц назад

Thanks!

@yuxiang4218 9 месяцев назад

clearly explained. Thanks!

@TechWithNikola 9 месяцев назад

Thank you!

@GlocOr33 9 месяцев назад

Thanks for the video that was very well explained especially coin change problem animation 👍👍

@TechWithNikola 9 месяцев назад

Thanks. I’m so glad you’ve liked it! 😀

@FrodoxDarkDragon 8 месяцев назад

I cannot wait for the second part :D

@TechWithNikola 8 месяцев назад

I'm glad :) Would you prefer to see more advanced DP problems for part 2? The alternative is to explain how to construct the solution path. For example, when I say path I mean what coins should we choose to get to sum 13. Right now, our solution says "you need 3 coins" but it would be nice to say "you need 3 coins: 4, 4, 5". I want to do both eventually, it's just the matter of choosing which one to do first.

@treelibrarian7618 8 месяцев назад

wonderful video! so well explained! I had a weird distorted view of what dynamic programming meant before this. while thinking about the maze problem it occurred that it's really a 2D Fibonacci series. also, only a 1d array is needed, reducing memory complexity and cache usage. you can even keep a running total for each column, initialized to 1, and forgo the initial setup (except for zeroing the array memory) halving the memory reads. in C looks like: int paths(int n, int m) { int t; if(m < n) { t = m; m = n; n = t; } // n rows is smaller dimension int memo[--n] = {0}; // reduce n by one since first row is handled by t = 1 below for(int i = 0; i < m; ++i) { // column counter t = 1; // first row always 1 for(int j = 0; j < n; ++j) { // row counter t = (memo[j] += t); // do the work } } return t; // we know what the final value was already } /// asm version (linux calling convention) .paths: cmp rdi, rsi cmovlt rax, rsi cmovlt rsi, rdi cmovlt rdi, rax dec rsi mov rcx, rsi mov rdx, rsp ;; using stack space directly for array xor rax, rax .zloop mov [rdx], rax ;; memory clearing (using int64's here) sub rdx, 8 sub rcx, 1 jnz zloop .iloop mov rax, 1 mov rcx, rsi mov rdx, rsp ;; reset running total, array address pointer and row count each column .jloop add rax, [rdx] ;; do the work mov [rdx], rax sub rdx, 8 ;; iterate sub rcx, 1 jnz jloop ;; inner loop should execute once per clock cycle sub rdi, 1 jnz iloop ret ;; result is already in rax, no registers needed to be spilled to stack

@TechWithNikola 8 месяцев назад

Thank you! I’m so glad to hear that this video cleared some things up. Your observations are correct. This is why I like bottom up approach more because it allows you to do these kinds of optimizations. I like the ASM solution 😀

@user-ov8ww9ul4z 6 месяцев назад

The smallest act of kindness is worth more than the grandest intention.

@JVLawnDarts Месяц назад

Watching your videos truly helped me better understand this for my final. Thanks brother, here’s hoping I can graduate

@TechWithNikola 27 дней назад

Good luck! I’m glad my videos were helpful

@jilherme 4 месяца назад

very easy to follow and entertaining!!

@TechWithNikola 4 месяца назад

Thank you!

@koushiksinha4822 8 месяцев назад

Loved your content, need more of these :)

@TechWithNikola 8 месяцев назад

Thanks :) More to come!

@hambi445 9 месяцев назад

Amazing video! hope to see more videos of yours

@TechWithNikola 9 месяцев назад

Thank you! Yeah, I’ll be making more videos.

@yzr5089 8 месяцев назад

Hey, I almost never comment, but your video is really amazing. After watching it and refreshing my brain about DP, I managed to solve a new medium DP question on Leetcode without help!! (DP is one of my weaknesses lol) I’m looking forward to watching your future video on harder DP questions!

@TechWithNikola 8 месяцев назад

Hey, thanks a lot for taking the time to comment. I’m glad you’ve found it useful!

@jst8922 5 месяцев назад

Which Leetcode problem it was ?

@Insomn3s 5 месяцев назад

Great educational video, thank you!

@TechWithNikola 5 месяцев назад

You’re welcome! Glad you liked it.

@aayushtheapple 5 месяцев назад

Great video! starting my DP journey from this one.

@TechWithNikola 5 месяцев назад

Thank you! Good luck. Feel free to ask here if you need any help :)

@sazh1 7 месяцев назад

There's a slight issue for Coin Problem: How many ways The given solution does not account for duplicates such as 1+1+2 and 1+2+1 (which together should count as 1 possible solution instead of 2) The example 5, [1,4,5] should have an output of 3: 1+1+1+1+1 1+4 5 But instead is 4 because it counts 4+1 as a separate solution to 1+4. An iterative solution that handles this would be for example: memo = defaultdict(int) memo[0] = 1 for coin in coins: for i in range(coin, amount + 1): memo[i] += memo[i-coin] return memo[amount]

@TechWithNikola 7 месяцев назад

Hello, thanks for the comment. > The given solution does not account for duplicates such as 1+1+2 and 1+2+1 (which together should count as 1 possible solution instead of 2) Why should this count as one solution? Note that the problem definition explicitly says that these should count as 2 solutions, and 1+4 and 4+1 are explicitly called out as an example (see example at 14:04).

@sazh1 7 месяцев назад

@@TechWithNikola oh ur right guess i just completely ignored that lol. If order matters then the given solution works.

@sazh1 7 месяцев назад

The problem does become interesting if duplicates were to be excluded though.

@khaledhamoul1403 5 месяцев назад

Awesome explanation, thank you very much

@TechWithNikola 5 месяцев назад

Thank you. Glad you’ve enjoyed it!

@doriandd4648 3 месяца назад

Great stuff and well explained.

@TechWithNikola Месяц назад

Thank you

@nicolaslupi3111 7 месяцев назад

Gold. Can't wait for the second part

@TechWithNikola 7 месяцев назад

Thanks. What would you like to see in part 2? Some options: - How to reconstruct the path that leads to optimal solution (e.g. which coins to choose for minimum number of coons) - more advanced dp problems - anything else

@nicolaslupi3111 7 месяцев назад

More advanced problems would be awesome. For example I was trying to solve a problem where you need to find the shortest path from one corner of a grid to another. Some cells have walls and you can only cross one of them (or k in the general case). Also you can only move up, down, left or right. Your video helped me a lot trying to solve this using DP but I'm still having trouble, specially trying to think the bottom up approach.

@TechWithNikola 7 месяцев назад

@@nicolaslupi3111thanks for suggestion. I’m glad the video helped. I’ll think of some advanced problems to cover in the next video. I may continue this series 1 problem per part from now on, to get videos out sooner.

@keeprocking3620 3 месяца назад

Top notch stuff

@TechWithNikola 3 месяца назад

Thanks

@fengyuan7838 4 месяца назад

simple and easy to understand

@TechWithNikola 4 месяца назад

Thank you :)

@sophiophile 4 месяца назад

Great video, the only thing I might recommend is adding a diagram explaining how `for i in range(1, m +1):` builds up the memo dict from the bottom up.

@TechWithNikola 4 месяца назад

Thanks. Yeah, that would have been useful.

@denisboksha8243 7 месяцев назад

Thank you

@fmictsang8874 8 месяцев назад

Its really helpful. Thanks.

@TechWithNikola 8 месяцев назад

You’re welcome! I’m glad you’ve found it useful.

@begula_chan 2 месяца назад

Thank you very much! It helped me understand basic concepts of DP a lot! You're a very cool guy.

@TechWithNikola Месяц назад

I’m glad to hear that. Thank you for the kind words

@kevintonbong3838 4 месяца назад

Thank you for this usefull and comprehensive way to explain the concept of dynamic programming. That's a realy good video, I watched it many times.

@TechWithNikola 4 месяца назад

You're welcome Kevin. Thank you for taking the time to comment. I really appreciate it!

@TanigaDanae 8 месяцев назад

Another solution for fibbonachi was the "sliding window" where you work your way up similar to the bottom up. Example in C size_t fib(size_t n) { size_t high = 1, low = 1, tmp; for (size_t i = 2; i < n; ++i) { // add low = high + low; // swap tmp = high; high = low; low = tmp; } return high; } Edit: I am not sure this is called dynamic programming.

@TechWithNikola 8 месяцев назад

Yup, this would work and use O(1) memory. This is the main advantage of the bottom-up approach because it makes it easy to reuse memory of memoized solutions that we don't need anymore.

@JavierFausLlopis 5 месяцев назад

Great explanation, thanks a lot for sharing. For us educators this is at least inspirational.

@TechWithNikola 5 месяцев назад

Thank you the comment. I’m glad you like the content 😀

@________.pathfinder 7 месяцев назад

Amazing, I think everyone should check it first before start learning DSA

@TechWithNikola 7 месяцев назад

Thank you!

@kentroglobalinvestmentllc8921 2 месяца назад

❤❤❤ I love your work sir

@TechWithNikola Месяц назад

Thank you ❤️

@KablammoManYT 5 месяцев назад

I love how you could just solve the maze one using combinations but you did it recursively anyway: import math def grid_paths(m,n): return math.factorial(m+n-2)/(math.factorial(m-1)*math.factorial(n-1))

@TechWithNikola 5 месяцев назад

Correct. The intent was to show ideas behind dynamic programming though. Other problems can also be solved differently, and in better time complexity - for example, fibonacci can be solved in O(lg N). One thing to keep in mind is that the dp approach can easily be extended to solve the maze problem with obstacles or other constraints.

@brokecoder Месяц назад

I think to only get good a DP, is to start thinking about problems that you tend to solve without DP, from the angle of DP.

@SRI-PRIYAN 5 месяцев назад

15:22 If you think for some time, you can arrive at the formula C(N + M - 2, N - 1) where C is the combinatorics function. Explanation: 1. The Rabbit has to take N - 1 steps down and M - 1 steps right to reach the bottom right cell. 2. So a total of (N - 1) + (M - 1) = N + M - 2 steps 3. From these N + M - 2 steps, we can "Choose" N - 1 steps that will be the downward steps. The remaining steps will be towards the right. Hence the formula C(N + M - 2, N - 1) 4. By symmetry, C(N + M - 2, M - 1) is also correct and will give the same answer. Note: C(n, r) = C(n, n - r)

@TechWithNikola 5 месяцев назад

Thank you for taking the time to write this. Yes, that’s correct. There have been a few mentions of this and I wrote the comment explaining how to do it. Maybe I should pin that given that almost all problems in this video have an alternative solution.

@genshen4703 5 месяцев назад

nice vid, keep going!

@TechWithNikola 5 месяцев назад

Thank you!

@nishantsrinivas2936 9 месяцев назад

Great video!!!

@TechWithNikola 9 месяцев назад

Thank you

@zemariagp 6 месяцев назад

DP all the way

@senargha 9 месяцев назад

Excellent video

@TechWithNikola 9 месяцев назад

Thank you

@self_lionized 6 месяцев назад

Absolutely beautiful

@TechWithNikola 6 месяцев назад

Thank you!

@Code_Creator123 8 месяцев назад

Great video, thanks 👍

@TechWithNikola 8 месяцев назад

Glad you enjoyed it

@yuris10101 6 месяцев назад

amazing explanation!

@TechWithNikola 6 месяцев назад

Thanks. Glad you liked it!

@sazk4000 9 месяцев назад

outstanding! 🙂

@TechWithNikola 9 месяцев назад

Thank you! 😀

@hyqhyp 7 месяцев назад

Part 2 please!

@TechWithNikola 4 месяца назад

Part 2 is here: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-rE5h11FwiVw.htmlsi=_dT9c6EOSpU_xa4A It's not as popular as part 1, but I do hope that it matches your expectations. Let me know! Any feedback is welcome.

@linkernick5379 9 месяцев назад

Very nicely presented and animated! 👍 What tool have you used to create it?

@TechWithNikola 8 месяцев назад

Thank you. This specific video uses combination of powerpoint and keynote. For other videos I’ve also used Manim library.

@emekaezekwem5677 7 месяцев назад

well put together

@TechWithNikola 7 месяцев назад

Thanks!

@chungtran2059 4 месяца назад

nice i love it

@TechWithNikola 4 месяца назад

Thank you! :)

@fireinthehole2272 6 месяцев назад

YOU ARE AMAZING THANK YOU

@TechWithNikola 6 месяцев назад

Thank you for the kind words! It makes me very happy when I hear that people enjoy my videos.

@akashagarwal6390 2 месяца назад

this is too good

@TechWithNikola Месяц назад

Thanks

@user-pr9un1qx4e 6 месяцев назад

Small opportunities are often the beginning of great enterprises.

@kovidkrishnan8038 3 месяца назад

eye opener

@TechWithNikola 3 месяца назад

Glad to hear that!

@olliecook1982 7 месяцев назад

Is there a syntax highlighting like that for c? I really like it

@littledragonwolf 4 месяца назад

Very good informative video. Thank you. Third problem can also be solved analytically (x+y-2) choose (x-1).

@TechWithNikola 4 месяца назад

You're welcome, and thank you for the comment. Yup, the third problem can be solved with simple combinatorics. It's still useful to learn DP in that way, because the problem can easily change to e.g. have obstacles in the board, and combinatorics don't work all of a sudden. :)