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

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

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

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.

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.

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

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

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

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

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

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

😂 thanks!

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.

You’re welcome!

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

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: ukposts.info/have/v-deo/qnVmnGdofa2at6s.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.

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!

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

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

Memoization you mean?

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

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

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! This means a lot to me.

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

Thank you!

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.

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

Thanks!

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.

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.

Thank you! I'm glad you've enjoyed 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.

Thanks :) More to come!

Thank you!

Thanks, glad you've enjoyed it :)

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 😀

Thanks a lot! Hopefully one day 😀

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

Thank you!

Thank you!

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.

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

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

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

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

Which Leetcode problem it was ?

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

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.

Yeah, that’s correct. I already mentioned these solutions in other comments. However, the goal here was to understand ideas in DP on simple problems, so I didn’t want to add extra information that may confuse newcomers.

Thank you!

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

That’s very interesting. It’s always nice to learn about new ways to solve a problem, so thank you for taking the time to write this in a comment. It’s appreciated!

Thank you

Thanks

You’re welcome! Glad you liked it.

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

Thank you

Thank you. Glad you’ve enjoyed it!

Thank you! 😀

Thank you!

Thank you

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

Thank you ❤️

Glad to hear that!

Thanks, I'm glad you've enjoyed the video. Regarding the tail recursion part, I don't think your statement is entirely accurate. I wouldn't say that function calls having stack overhead is a language implementation choice. You can only apply tailcall optimization if the function call is the last instruction in the recursive function. For example, what would the assemebly instructions look like for the following code (some arbitrary function): int f(int n) { if (n == 0) { return 0; } int k = 3 + f(n - 1) * 2; return k + f(n - 2); } My claim is that the f(n-1) call cannot be optimized as a jump instruction. It would have to be a call instruction because the program would have to remember the next instruction to process, and the state of local variables of f. Am I missing something?

Great summary. I agree with all your points. > But if that's possible, can't the bottom-up approach do the same, after a bit of thinking? It's difficult to track which problem to solve next with the bottom-up approach. We need a topological sort of the problems, which may be simple for some problems, but hard to generalize. If the problem space is sparse, then there's a good chance that we can solve the problem without DP.

​@@TechWithNikola > Great summary Thanks. > It's difficult to track which problem to solve next with the bottom-up approach. We need a Topological sort [...]. Yes, that's a good point! The bottom-up approach walks the argument/subproblem space in topological order, from sink-most to source-most. The the top-down approach simply walks all the out-edges from the current grid cell. Checking for cached results enables us to ignore the topological ordering and discover enough information about it on the go. > If the problem space is sparse, then there's a good chance that we can solve the problem without DP. Hm. Interesting. Hm. This is not obvious to me. Can you illustrate this principle with a few examples?

​@@jonaskoelker > Can you illustrate this principle with a few examples? I'm just saying this from intuition, so take it with a grain of salt. I can't provide an example to generalize my statement because every problem is unique. The main reason is that I find it hard to imagine an interesting DP-like problem with the sparse solution space. It would be easier to think about this if you can find a problem, then we can try to solve it and maybe draw some conclusions. I attempted to phrase some of these problems so that the solution space is sparse, but I failed to come up with anything interesting. E.g. the minimum coin problem with sparse solution space would be something like "coin values are very large". Then instead of iterating over each solution with a for loop, we would compute possible solutions and add them to the queue (like a BFS algorithm maybe?). But this is just a direct way of coming up with the topological ordering that is specific to the problem. Sorry but I don't have a better answer at this point. I'll comment if I can think of anything interesting.

@@TechWithNikola I see. I figure the applicability of DP has to do with reusing solutions to subproblems. Of course, just because a DP solution exists doesn't mean a non-DP solution doesn't exist. I guess in some sense there is _always_ (or almost always) a non-DP solution: brute force. So maybe the thing to look for is the kind of problem where DP works but is not the simplest solution. A leetcode example comes to mind: sliding window maximum. Given an array A of length n and a window size k, return `[max(a[i:i+k]) for i in range(approximately n - k + 1)]`. Given the maximum across a window of length (k-1) we can easily compute the maximum across a window of size k if it contains the smaller window. So DP applies. But it takes quadratic space (and thus time), and there is a solution which only takes linear space and time. (My first such solution involves rot13(pnegrvna gerrf).)

Oh, I should add: the sliding window maximum problem is relatively easy because we're computing the maximum for all windows simultaneously. There's a highly fancy data structure that uses linear space and lets us compute range maxima (or minima) in O(1) time per query, without the queries being batched. Erik DeMaine talks about it in one of his "Advanced Data Structures" lectures on OCW. It's on youtube. He talks in terms of RMQ: range _minimum_ queries. It turns out to relate to least common ancestor queries, so maybe looking for a lecture on trees will help you find it. [But no one will independently rediscover this in the context of a leet code problem. The batched window maximum problems seems of appropriate difficulty relative to the kind of leet code problems I'm familiar with.]

Glad you enjoyed it

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

Thank you!

Thanks. Glad you liked it!

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

Part 2 is here: ukposts.info/have/v-deo/qnVmnGdofa2at6s.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.

Thanks!

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

Thank you!

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

Thank you!

Hello. Yeah, that idea seems right (i haven't checked the formula though). It's definitely possible to solve this using simple combinatorics. You should be able to compute the number of ways to get to the bottom-right corner by rephrasing the problem as in how many ways can we choose [M-1] right (or [N-1] down) turns for the rabbit out of (N+M-2) turns, then use en.wikipedia.org/wiki/Binomial_coefficient formula to compute the solution: ([N+M-2] choose [M-1]). For example, the bigger grid in the video can be computed as (92 choose 18) (see www.wolframalpha.com/input?i=92+choose+18)

@@TechWithNikola thanks! I completely forgot the formula has a name

Thanks! ❤️

Thank you.