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

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

​@@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.

​@@tantalus_complexnice comment

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

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.

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

Can you explain where you got this formula?

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

@@aqfj5zy what are you waffling about, blud.

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

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.

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.

Can I ask something

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

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.

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

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.

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.

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

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

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

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?

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? 😊

@@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 :)

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.

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.

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

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

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

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.

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

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

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

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

You’re welcome!

Thanks a lot! Hopefully one day 😀

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: kzfaq.info/get/bejne/qKtlm5Riq93Nhqs.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.

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

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

Which Leetcode problem it was ?

Thank you!

Thanks!

Thank you! This means a lot to me.

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 😀

Thank you!

Good luck! I’m glad my videos were helpful

Thanks, glad you've enjoyed it :)

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.

Thanks :) More to come!

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

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

Thank you for the kind words! ❤️

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

Thanks. Yeah, that would have been useful.

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

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

Memoization you mean?

😂 thanks!

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

Thank you!

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

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.

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

Thanks!

Thank you!

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

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.

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

Thank you!

Thank you

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

Thanks

Thank you!

You’re welcome! Glad you liked it.

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

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

Thank you. Glad you’ve enjoyed it!

Thank you

Thank you! 😀

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

Glad you enjoyed it

Thanks. Glad you liked it!

Thank you ❤️

Thank you

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

Thanks!

Thank you! :)

Thank you :)

Glad to hear that!

Thanks

Thank you!

Thank you!

Hi, apologies for the late response. Thanks. I use a combination of: - powerpoint - keynote - manim - adobe premiere

Hi, glad to hear that. I use the following: - Keynote - Powerpoint - Manim - Adobe Premiere

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. :)

Part 2 is here: kzfaq.info/get/bejne/qKtlm5Riq93Nhqs.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.

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

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

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

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.

Thank you. Next one will be dynamic programming 2 😀

Hey, I have used mostly powerpoint for this video, but I also use keynote and Manim (python library).

Thanks! ❤️

Thank you :-) If you are referring to the topological sort order part, my reasoning was that sorting the graph in the topological order means that node u comes before node v if there is an edge from u to v. I probably used this article at the time: en.m.wikipedia.org/wiki/Topological_sorting

Thanks mate!

You're welcome! You could maybe look at it like that, but I wouldn't use that exact phrasing to describe DP. I think the general idea when we say DP is "solve small independent problems and use them to solve bigger problems". You're right that we are using memory to store solution for each sub-problem, and we have to (with the exception for solutions that are not required anymore).