title
DP 22. Coin Change 2 | Infinite Supply Problems | DP on Subsequences

description
Lecture Notes/C++/Java Codes: https://takeuforward.org/dynamic-programming/striver-dp-series-dynamic-programming-problems/ Problem Link: https://bit.ly/33Kd8o2 Pre-req for this Series: https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9 a Make sure to join our telegram group for discussions: https://linktr.ee/takeUforward Full Playlist: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY In this video, we solve the problem of ways to form Coin Change. We start with memoization, then tabulation, then two-row space optimization. This problem is the eighth problem on DP on Subsequences Pattern. Please watch DP 14 before watching this. If you have not yet checked our SDE sheet, you should definitely do it: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/ You can also get in touch with me at my social handles: https://linktr.ee/takeUforward

detail
{'title': 'DP 22. Coin Change 2 | Infinite Supply Problems | DP on Subsequences', 'heatmap': [{'end': 604.866, 'start': 582.906, 'weight': 1}, {'end': 965.285, 'start': 932.357, 'weight': 0.794}, {'end': 1128.915, 'start': 1095.481, 'weight': 0.92}, {'end': 1163.433, 'start': 1149.666, 'weight': 0.759}], 'summary': "Covers dynamic programming solutions for coin change problem, subsequences problem, time and space complexity, and implementation techniques, emphasizing recursion, tabulation, memoization, and efficient computation with 'long' data type, encouraging engagement.", 'chapters': [{'end': 298.655, 'segs': [{'end': 29.554, 'src': 'embed', 'start': 0.109, 'weight': 0, 'content': [{'end': 2.009, 'text': 'hey, everyone, welcome back to take you forward.', 'start': 0.109, 'duration': 1.9}, {'end': 11.571, 'text': 'so today we will be solving the 22nd lecture of the dynamic programming playlist and we have been containing with the problems with dp on sub sequences.', 'start': 2.009, 'duration': 9.562}, {'end': 13.191, 'text': 'so today we will be solving the problem.', 'start': 11.571, 'duration': 1.62}, {'end': 15.972, 'text': 'ways to make a coin change.', 'start': 13.191, 'duration': 2.781}, {'end': 17.692, 'text': 'now, what does the problem states?', 'start': 15.972, 'duration': 1.72}, {'end': 26.453, 'text': "you'll, you'll be given an array, okay, and the array will contain elements like one, two, three, whatever it can, and you have to form this target.", 'start': 17.692, 'duration': 8.761}, {'end': 29.554, 'text': "so you might be like, let's say, we've done this problem.", 'start': 26.453, 'duration': 3.101}], 'summary': "Solving the 22nd lecture of dynamic programming playlist, focusing on 'ways to make a coin change' problem.", 'duration': 29.445, 'max_score': 0.109, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk109.jpg'}, {'end': 210.576, 'src': 'embed', 'start': 167.454, 'weight': 1, 'content': [{'end': 175.542, 'text': 'where i said whenever the problem say states total number of ways, a base case will always return one if, if the destination is made,', 'start': 167.454, 'duration': 8.088}, {'end': 179.048, 'text': 'or else it will return zero if the destination is not met.', 'start': 176.747, 'duration': 2.301}, {'end': 185.669, 'text': "And you'll try out all possibilities, and the summation of all possibilities will be returning the total number of ways.", 'start': 179.468, 'duration': 6.201}, {'end': 186.869, 'text': 'So over here.', 'start': 186.089, 'duration': 0.78}, {'end': 187.589, 'text': 'what is the problem?', 'start': 186.869, 'duration': 0.72}, {'end': 192.57, 'text': 'stating?. So, in order to write the recursion, you have to write the recurrence right?', 'start': 187.589, 'duration': 4.981}, {'end': 193.991, 'text': 'So how do you write the recurrence?', 'start': 192.97, 'duration': 1.021}, {'end': 196.131, 'text': "I've taught you three ways.", 'start': 194.011, 'duration': 2.12}, {'end': 197.351, 'text': 'What are the three ways?', 'start': 196.551, 'duration': 0.8}, {'end': 202.689, 'text': 'The first is express, in terms of specifically index.', 'start': 197.431, 'duration': 5.258}, {'end': 210.576, 'text': 'over here we have an array, so we can definitely use index to express, and the other thing will be target that we will be using to express right.', 'start': 202.689, 'duration': 7.887}], 'summary': 'Recursion for finding total number of ways using index and target.', 'duration': 43.122, 'max_score': 167.454, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk167454.jpg'}], 'start': 0.109, 'title': 'Coin change problem and recursion', 'summary': "Covers solving the 'ways to make a coin change' problem using dynamic programming to find different ways to form a target from a given array, and discusses counting the total number of ways using recursion, emphasizing base cases and summing up all possibilities to calculate the total number of ways.", 'chapters': [{'end': 96.325, 'start': 0.109, 'title': 'Coin change problem', 'summary': "Covers solving the problem 'ways to make a coin change' by using dynamic programming to find the different ways to form a target using the given array, where each element can be used any number of times.", 'duration': 96.216, 'highlights': ['The problem involves finding the different ways to form a target using the given array, where each element can be used any number of times, presenting a unique challenge compared to previous problems where elements could only be used once.', 'The approach involves using dynamic programming to determine the number of ways to make a coin change, allowing for the repetition of elements to form the target.', 'The example demonstrates the flexibility of using elements multiple times to reach the target, showcasing the multiple combinations possible to achieve the desired sum.']}, {'end': 187.589, 'start': 96.325, 'title': 'Counting total number of ways using recursion', 'summary': 'Discusses counting the total number of ways using recursion, emphasizing the importance of base cases returning 1 if the destination is achieved and 0 if not, and summing up all possibilities to calculate the total number of ways.', 'duration': 91.264, 'highlights': ['Emphasizes the importance of base cases returning 1 if the destination is achieved and 0 if not, in counting the total number of ways.', 'Summing up all possibilities to calculate the total number of ways is a key concept in recursion.', 'Recursion is used to try out all possibilities and count the total number of ways.']}, {'end': 298.655, 'start': 187.589, 'title': 'Recursion and index expression', 'summary': 'Discusses writing recurrences for recursion using index expression, exploring all possibilities, and summing all possibilities to return the total number of ways, illustrated using an example of forming a target from an array.', 'duration': 111.066, 'highlights': ['The process of writing recurrences for recursion involves expressing in terms of index, exploring all possibilities, and summing all possibilities to return the total number of ways, with an example of forming a target from an array.', 'The three ways to write recurrences for recursion are expressing in terms of index, exploring all possibilities, and summing all possibilities to return the total number of ways.', 'Illustrating the concept of forming a target from an array by using index expression and exploring all possibilities to find the total number of ways to form the target.']}], 'duration': 298.546, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk109.jpg', 'highlights': ['The approach involves using dynamic programming to determine the number of ways to make a coin change, allowing for the repetition of elements to form the target.', 'Emphasizes the importance of base cases returning 1 if the destination is achieved and 0 if not, in counting the total number of ways.', 'The process of writing recurrences for recursion involves expressing in terms of index, exploring all possibilities, and summing all possibilities to return the total number of ways, with an example of forming a target from an array.']}, {'end': 482.414, 'segs': [{'end': 324.325, 'src': 'embed', 'start': 298.655, 'weight': 0, 'content': [{'end': 308.158, 'text': "you can either take this guy and you say, okay, this particular guy will be a part of the sequence that i'm looking to form.", 'start': 298.655, 'duration': 9.503}, {'end': 311.479, 'text': "so you'll be like, okay, i can take it or i'll not take it again.", 'start': 308.158, 'duration': 3.321}, {'end': 313.08, 'text': 'what are the possibilities?', 'start': 311.479, 'duration': 1.601}, {'end': 321.042, 'text': "i will either not take it or either I'll take it in all the DP on subsequences problem.", 'start': 313.08, 'duration': 7.962}, {'end': 324.325, 'text': "It has to be either I'll not take it or either I'll take it.", 'start': 321.322, 'duration': 3.003}], 'summary': 'Deciding whether to include a particular guy in a sequence involves making a binary decision, leading to two possibilities: taking it or not taking it.', 'duration': 25.67, 'max_score': 298.655, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk298655.jpg'}, {'end': 415.204, 'src': 'embed', 'start': 347.756, 'weight': 1, 'content': [{'end': 352.184, 'text': "And what will happen to the target? If I'm not taking any guy, the target still remains same.", 'start': 347.756, 'duration': 4.428}, {'end': 356.158, 'text': 'So it will be the same thing and we will move to the previous index.', 'start': 352.697, 'duration': 3.461}, {'end': 357.758, 'text': 'But what about take??', 'start': 356.698, 'duration': 1.06}, {'end': 363.179, 'text': 'Again, whenever there are cases for take, you have to consider can you actually take it??', 'start': 358.338, 'duration': 4.841}, {'end': 369.66, 'text': 'Because assume this is the array and you have a four over here and this is the index and the target is five.', 'start': 363.279, 'duration': 6.381}, {'end': 371.56, 'text': 'Then you can definitely take it.', 'start': 370.22, 'duration': 1.34}, {'end': 372.981, 'text': 'You can definitely take it.', 'start': 371.84, 'duration': 1.141}, {'end': 376.121, 'text': 'But what if the target is two? Then you cannot take it.', 'start': 373.401, 'duration': 2.72}, {'end': 380.042, 'text': 'So you need to make sure initially take is zero.', 'start': 376.601, 'duration': 3.441}, {'end': 386.826, 'text': "And if array of index is lesser than equal to the target that you're looking for?", 'start': 380.805, 'duration': 6.021}, {'end': 392.808, 'text': "yes, if array of index is lesser than equal to the target that you're looking for, then you can definitely take it.", 'start': 386.826, 'duration': 5.982}, {'end': 397.829, 'text': 'And if you take it, the target is going to reduce by array of index.', 'start': 393.328, 'duration': 4.501}, {'end': 400.93, 'text': 'But what will happen to index? That is the question.', 'start': 398.349, 'duration': 2.581}, {'end': 410.479, 'text': "now remember one thing in all, the question which states can be used any number of times, you don't move back to the previous index.", 'start': 401.77, 'duration': 8.709}, {'end': 413.682, 'text': 'i repeat you do not move back to the previous index.', 'start': 410.479, 'duration': 3.203}, {'end': 415.204, 'text': 'that is the thumb rule.', 'start': 413.682, 'duration': 1.522}], 'summary': 'Consider target & array index to determine if you can take it, reducing target accordingly.', 'duration': 67.448, 'max_score': 347.756, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk347756.jpg'}, {'end': 482.414, 'src': 'embed', 'start': 432.153, 'weight': 3, 'content': [{'end': 439.576, 'text': 'so make sure you say i will still stay at the same index because this index might be picked at the next instance.', 'start': 432.153, 'duration': 7.423}, {'end': 449.066, 'text': 'so please stay at the same index and right over here i will say return, not take, plus, take.', 'start': 439.576, 'duration': 9.49}, {'end': 450.226, 'text': "that is what i'll do.", 'start': 449.066, 'duration': 1.16}, {'end': 451.867, 'text': "so once i've written this.", 'start': 450.226, 'duration': 1.641}, {'end': 453.247, 'text': "it's simple enough.", 'start': 451.867, 'duration': 1.38}, {'end': 459.95, 'text': 'so remember this whenever the problem states any number of times.', 'start': 453.247, 'duration': 6.703}, {'end': 466.852, 'text': 'in all the take cases this is the funda you stay at the same index and apart from that, everything stays same.', 'start': 459.95, 'duration': 6.902}, {'end': 469.693, 'text': 'so what will be the base case?', 'start': 466.852, 'duration': 2.841}, {'end': 470.494, 'text': 'what did i say you?', 'start': 469.693, 'duration': 0.801}, {'end': 473.275, 'text': 'how do you think of base cases when you write?', 'start': 470.494, 'duration': 2.781}, {'end': 478.154, 'text': "i've taught you the way you are starting the recursion from n minus one.", 'start': 473.275, 'duration': 4.879}, {'end': 480.574, 'text': 'you write it for the last index.', 'start': 478.154, 'duration': 2.42}, {'end': 482.414, 'text': "that's zero, for sure.", 'start': 480.574, 'duration': 1.84}], 'summary': 'The key point is to stay at the same index, and to handle base case for the last index at zero.', 'duration': 50.261, 'max_score': 432.153, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk432153.jpg'}], 'start': 298.655, 'title': 'Decision making in subsequences problem and recursion in programming', 'summary': 'Discusses the decision-making process and impact on target value and index movement in subsequences problem, and the concept of recursion with emphasis on staying at the same index and the base case at index zero.', 'chapters': [{'end': 415.204, 'start': 298.655, 'title': 'Decision making in subsequences problem', 'summary': 'Discusses the decision-making process of taking or not taking a particular element within a sequence to form subsequences, emphasizing the conditions for taking or not taking and the impact on the target value and index movement.', 'duration': 116.549, 'highlights': ['The key to solving any specific problem in subsequences lies in the decision-making process of whether to take or not take an element, with the possibilities being either not taking or taking it (5 occurrences).', 'When not taking an element, the movement to the next index occurs, while the target value remains the same (4 occurrences).', "For the 'take' scenario, the condition for taking an element is determined by comparing the array value at the index with the target value, and if it is less than or equal to the target, it can be taken, impacting the reduction of the target value (4 occurrences).", 'In cases where an element can be used any number of times, there is no movement back to the previous index, serving as a crucial rule in the decision-making process (2 occurrences).']}, {'end': 482.414, 'start': 415.204, 'title': 'Recursion and base case in programming', 'summary': 'Discusses the concept of recursion and emphasizes the importance of staying at the same index in certain cases, with a focus on the base case being at index zero.', 'duration': 67.21, 'highlights': ['Emphasize staying at the same index when the problem states any number of times, leading to a simple approach.', 'Highlight the importance of the base case at index zero when starting the recursion, as it forms the fundamental starting point for the process.']}], 'duration': 183.759, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk298655.jpg', 'highlights': ['The key to solving any specific problem in subsequences lies in the decision-making process of whether to take or not take an element, with the possibilities being either not taking or taking it (5 occurrences).', 'When not taking an element, the movement to the next index occurs, while the target value remains the same (4 occurrences).', "For the 'take' scenario, the condition for taking an element is determined by comparing the array value at the index with the target value, and if it is less than or equal to the target, it can be taken, impacting the reduction of the target value (4 occurrences).", 'Emphasize staying at the same index when the problem states any number of times, leading to a simple approach.', 'Highlight the importance of the base case at index zero when starting the recursion, as it forms the fundamental starting point for the process.', 'In cases where an element can be used any number of times, there is no movement back to the previous index, serving as a crucial rule in the decision-making process (2 occurrences).']}, {'end': 950.44, 'segs': [{'end': 604.866, 'src': 'heatmap', 'start': 582.906, 'weight': 1, 'content': [{'end': 594.5, 'text': 'if target modulated array of 0 is equal to equal to 0, this will return a 1, or else it will return a 0 if the condition is false.', 'start': 582.906, 'duration': 11.594}, {'end': 599.003, 'text': 'that makes sense because the coins are of denomination greater than equal to one.', 'start': 594.5, 'duration': 4.503}, {'end': 600.824, 'text': 'if it was of zero.', 'start': 599.003, 'duration': 1.821}, {'end': 604.866, 'text': "you can watch the dp 18, where i've covered this case already.", 'start': 600.824, 'duration': 4.042}], 'summary': 'Array with target modulated by 0 returns 1, else 0. explained in dp 18 video.', 'duration': 21.96, 'max_score': 582.906, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk582906.jpg'}, {'end': 629.202, 'src': 'embed', 'start': 604.866, 'weight': 4, 'content': [{'end': 611.89, 'text': "i've already covered this case in dp 18 problem, right when the denomination might be of 0, and you're reaching the base case.", 'start': 604.866, 'duration': 7.024}, {'end': 613.831, 'text': "but as of now, let's keep it simple.", 'start': 611.89, 'duration': 1.941}, {'end': 617.813, 'text': 'so you have figured out that this will be the recurrence whenever we reach the end.', 'start': 613.831, 'duration': 3.982}, {'end': 619.794, 'text': 'this will be the base case.', 'start': 618.553, 'duration': 1.241}, {'end': 621.235, 'text': 'can that target?', 'start': 619.794, 'duration': 1.441}, {'end': 624.558, 'text': 'because i can pick up the array element any number of times.', 'start': 621.235, 'duration': 3.323}, {'end': 629.202, 'text': "so if it is divisible, i'll pick it any number of times and i'll make the t.", 'start': 624.558, 'duration': 4.644}], 'summary': 'Discussing recurrence and base case for picking array elements multiple times.', 'duration': 24.336, 'max_score': 604.866, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk604866.jpg'}, {'end': 750.251, 'src': 'embed', 'start': 688.181, 'weight': 1, 'content': [{'end': 695.043, 'text': "so generally an interview you can call, you can just say if you're in an interview you'll be saying that recursion will be exponential.", 'start': 688.181, 'duration': 6.862}, {'end': 696.604, 'text': 'so i have to use memoization.', 'start': 695.043, 'duration': 1.561}, {'end': 698.385, 'text': 'so recursion is exponential.', 'start': 696.604, 'duration': 1.781}, {'end': 699.705, 'text': 'and what about the?', 'start': 698.385, 'duration': 1.32}, {'end': 701.206, 'text': 'this is the time complexity.', 'start': 699.705, 'duration': 1.501}, {'end': 702.786, 'text': 'what about the space complexity?', 'start': 701.206, 'duration': 1.58}, {'end': 711.375, 'text': "again, if i'm talking about space complexity, since you're standing at the same index, auxiliary stack, space will be not a big orphan right.", 'start': 702.786, 'duration': 8.589}, {'end': 717.885, 'text': 'because assume you just have one, two, okay, and the target is 10..', 'start': 711.375, 'duration': 6.51}, {'end': 718.426, 'text': 'picking this two.', 'start': 717.885, 'duration': 0.541}, {'end': 719.107, 'text': "you're picking this two.", 'start': 718.426, 'duration': 0.681}, {'end': 720.308, 'text': "you're picking this two.", 'start': 719.107, 'duration': 1.201}, {'end': 723.412, 'text': 'so it might go on, because five times you can pick this two.', 'start': 720.308, 'duration': 3.104}, {'end': 725.414, 'text': 'because five times you can pick this two.', 'start': 723.412, 'duration': 2.002}, {'end': 728.117, 'text': 'so it might go on up to a depth of five, right?', 'start': 725.414, 'duration': 2.703}, {'end': 731.12, 'text': 'so the auxiliary space is again greater than b?', 'start': 728.117, 'duration': 3.003}, {'end': 734.064, 'text': 'go of n, or i can say the worst case.', 'start': 731.12, 'duration': 2.944}, {'end': 735.585, 'text': 'at the worst case it can be b?', 'start': 734.064, 'duration': 1.521}, {'end': 737.287, 'text': 'go of target.', 'start': 735.585, 'duration': 1.702}, {'end': 748.409, 'text': 'assuming, assuming this case where you have an one and you have a target, not not exactly one you can say you have something like this one one.', 'start': 737.287, 'duration': 11.122}, {'end': 750.251, 'text': 'you have a one and the target is ten.', 'start': 748.409, 'duration': 1.842}], 'summary': 'Recursion has exponential time complexity, but space complexity is not a big concern for auxiliary stack.', 'duration': 62.07, 'max_score': 688.181, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk688181.jpg'}, {'end': 824.293, 'src': 'embed', 'start': 803.186, 'weight': 0, 'content': [{'end': 812.909, 'text': 'and the other another one over here if the state is not visited while a line right, and that will convert this into a memoization solution.', 'start': 803.186, 'duration': 9.723}, {'end': 817.811, 'text': 'so the moment you convert this into a memoization solution, the time complexity becomes b,', 'start': 812.909, 'duration': 4.902}, {'end': 824.293, 'text': 'go of n into target and the space complexity becomes n into target, plus an auxiliary target.', 'start': 817.811, 'duration': 6.482}], 'summary': 'Converting to memoization solution reduces time complexity to o(n*target) and space complexity to n*target.', 'duration': 21.107, 'max_score': 803.186, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk803186.jpg'}], 'start': 482.414, 'title': 'Recursion, time, and space complexity', 'summary': 'Covers forming a target sum with given coins, base case for recursion, and exponential time complexity. it also explores space complexity, conversion of recursion into memoization, tabulation for optimization, with o(n*target) time complexity and n*target space complexity.', 'chapters': [{'end': 702.786, 'start': 482.414, 'title': 'Recursion and time complexity', 'summary': 'Explains the logic of forming a target sum with given coins, the base case for recursion, and the exponential time complexity of the algorithm.', 'duration': 220.372, 'highlights': ['The base case for the recursion is established by checking if the target modulo the array element at index 0 is equal to 0, returning 1 if true and 0 if false.', 'The time complexity of the recursion is discussed, with the observation that for a given index, there can be more than two possible ways, leading to an exponential time complexity.', 'The need for memoization to reduce the time complexity is highlighted, as recursion alone results in exponential complexity, making it important to optimize the algorithm.']}, {'end': 803.186, 'start': 702.786, 'title': 'Space complexity in recursion', 'summary': 'Discusses the space complexity in recursion, with the auxiliary space being greater than o(n) or even o(target) in the worst case, and also explores the conversion of recursion into memoization through overlapping subproblems and dynamic programming arrays.', 'duration': 100.4, 'highlights': ['The worst-case auxiliary space complexity can be O(target), demonstrated by the example of a one and a target of ten, resulting in a depth of auxiliary stack space being ten.', 'The space complexity in recursion can be greater than O(n) in the worst case, as illustrated by the scenario of repeatedly picking a number two, leading to a depth of five and thus a larger auxiliary space.']}, {'end': 950.44, 'start': 803.186, 'title': 'Tabulation for memoization optimization', 'summary': 'Discusses the optimization of a memoization solution using tabulation, with a time complexity of o(n*target) and a space complexity of n*target, while also addressing the rules and steps for applying tabulation.', 'duration': 147.254, 'highlights': ['The time complexity of the memoization solution becomes O(n*target) and the space complexity becomes n*target, plus an auxiliary stack space of n*target.', 'The chapter explains the steps to apply tabulation, including defining the base case, identifying the changing parameters (index and target), and copying the recurrence.', 'The base case is operated at index equal to zero, with the condition T modulated array of zero equal to zero being stored in the state for any given P coming into the state.']}], 'duration': 468.026, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk482414.jpg', 'highlights': ['The time complexity of the memoization solution becomes O(n*target) and the space complexity becomes n*target, plus an auxiliary stack space of n*target.', 'The need for memoization to reduce the time complexity is highlighted, as recursion alone results in exponential complexity, making it important to optimize the algorithm.', 'The worst-case auxiliary space complexity can be O(target), demonstrated by the example of a one and a target of ten, resulting in a depth of auxiliary stack space being ten.', 'The space complexity in recursion can be greater than O(n) in the worst case, as illustrated by the scenario of repeatedly picking a number two, leading to a depth of five and thus a larger auxiliary space.', 'The base case for the recursion is established by checking if the target modulo the array element at index 0 is equal to 0, returning 1 if true and 0 if false.']}, {'end': 1164.574, 'segs': [{'end': 1007.647, 'src': 'embed', 'start': 951.18, 'weight': 0, 'content': [{'end': 965.285, 'text': 'What about the conversion? What about index? Can I say the index will be converted from where? You are running the recursion from n-1 till 0.', 'start': 951.18, 'duration': 14.105}, {'end': 968.306, 'text': 'So what is tabulation? Tabulation is bottom-up recursion.', 'start': 965.285, 'duration': 3.021}, {'end': 976.329, 'text': 'And in bottom up, the base case was the case of index equal to 0.', 'start': 971.246, 'duration': 5.083}, {'end': 979.371, 'text': 'So what is the next case? Index equal to 1.', 'start': 976.329, 'duration': 3.042}, {'end': 983.594, 'text': 'So you take index 0, build index 1, then index 2, then index 3.', 'start': 979.371, 'duration': 4.223}, {'end': 987.037, 'text': 'So thereby, you start from 1 and you go on till n minus 1.', 'start': 983.594, 'duration': 3.443}, {'end': 987.797, 'text': "It's the opposite.", 'start': 987.037, 'duration': 0.76}, {'end': 991.159, 'text': 'What about the target? The target will have similar consequences.', 'start': 988.177, 'duration': 2.982}, {'end': 993.461, 'text': 'You move from t to 0.', 'start': 991.56, 'duration': 1.901}, {'end': 996.403, 'text': "So you'll move from 0 to t over here.", 'start': 993.461, 'duration': 2.942}, {'end': 998.444, 'text': "You'll move from 0 to t over here.", 'start': 996.543, 'duration': 1.901}, {'end': 1000.005, 'text': 'Index done, target done.', 'start': 998.884, 'duration': 1.121}, {'end': 1007.647, 'text': 'just copy the recurrence, whatever you wrote, and if you are able to do this, you can easily solve this particular problem.', 'start': 1001.946, 'duration': 5.701}], 'summary': 'Tabulation involves bottom-up recursion, moving from 0 to t, and copying the recurrence for problem-solving.', 'duration': 56.467, 'max_score': 951.18, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk951180.jpg'}, {'end': 1164.574, 'src': 'heatmap', 'start': 1149.666, 'weight': 4, 'content': [{'end': 1152.727, 'text': 'just include it.', 'start': 1149.666, 'duration': 3.061}, {'end': 1155.108, 'text': 'it gave a strong answer, i think the most.', 'start': 1152.727, 'duration': 2.381}, {'end': 1161.613, 'text': "the reason should be this quickly, just change this off into long, long, and now let's try submitting this.", 'start': 1155.108, 'duration': 6.505}, {'end': 1163.433, 'text': 'so make sure you define everything as long.', 'start': 1161.613, 'duration': 1.82}, {'end': 1164.574, 'text': "okay. so what's the next thing?", 'start': 1163.433, 'duration': 1.141}], 'summary': 'The response was strong, emphasizing the need for quick change to long, detailed definitions.', 'duration': 69.093, 'max_score': 1149.666, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk1149666.jpg'}], 'start': 951.18, 'title': 'Solving coding problems with dynamic programming', 'summary': "Discusses tabulation and recursion in solving the index and target problem, focusing on the process of bottom-up recursion and moving from n-1 till 0 and t to 0, and dynamic programming with memoization technique and the requirement to define data types as 'long' for efficient computation.", 'chapters': [{'end': 1007.647, 'start': 951.18, 'title': 'Tabulation and recursion in index and target problem', 'summary': 'Discusses tabulation and recursion in solving the index and target problem, focusing on the process of bottom-up recursion and moving from n-1 till 0 and t to 0, to easily solve the problem.', 'duration': 56.467, 'highlights': ['The process of tabulation and recursion in solving the index and target problem is described, focusing on the bottom-up recursion technique, moving from n-1 till 0 and t to 0, to easily solve the problem.', 'The base case for bottom-up recursion is when the index is equal to 0, followed by the next case when the index is equal to 1, and the process continues till n minus 1.', 'The approach also involves moving from t to 0, which is the opposite direction, and copying the recurrence to solve the problem more easily.']}, {'end': 1164.574, 'start': 1007.647, 'title': 'Dynamic programming in coding', 'summary': "Discusses dynamic programming to solve a coding problem, emphasizing the use of a memoization technique and the requirement to define data types as 'long' for efficient computation.", 'duration': 156.927, 'highlights': ['The speaker discusses writing a recursive function to solve a given coding problem, with a focus on the index, target, and array values, indicating a potential issue with time limit exceeded (TLE) during execution.', 'The next step involves utilizing a vector and passing it by reference to optimize the code, while emphasizing the importance of memoization for efficient computation.', "Additionally, the speaker advises defining all variables as 'long' to ensure accurate computation and avoid potential errors during the code execution."]}], 'duration': 213.394, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk951180.jpg', 'highlights': ['The process of tabulation and recursion in solving the index and target problem is described, focusing on the bottom-up recursion technique, moving from n-1 till 0 and t to 0, to easily solve the problem.', 'The approach also involves moving from t to 0, which is the opposite direction, and copying the recurrence to solve the problem more easily.', 'The base case for bottom-up recursion is when the index is equal to 0, followed by the next case when the index is equal to 1, and the process continues till n minus 1.', 'The speaker discusses writing a recursive function to solve a given coding problem, with a focus on the index, target, and array values, indicating a potential issue with time limit exceeded (TLE) during execution.', 'The next step involves utilizing a vector and passing it by reference to optimize the code, while emphasizing the importance of memoization for efficient computation.', "Additionally, the speaker advises defining all variables as 'long' to ensure accurate computation and avoid potential errors during the code execution."]}, {'end': 1327.952, 'segs': [{'end': 1266.665, 'src': 'embed', 'start': 1237.633, 'weight': 0, 'content': [{'end': 1242.318, 'text': 'so just make sure this is over here and not just erase this.', 'start': 1237.633, 'duration': 4.685}, {'end': 1242.998, 'text': 'I think should be fine.', 'start': 1242.318, 'duration': 0.68}, {'end': 1244.24, 'text': "now let's try running this.", 'start': 1242.998, 'duration': 1.242}, {'end': 1246.287, 'text': 'Fine, it does run.', 'start': 1245.606, 'duration': 0.681}, {'end': 1247.268, 'text': "Let's submit this.", 'start': 1246.767, 'duration': 0.501}, {'end': 1248.128, 'text': 'It does.', 'start': 1247.868, 'duration': 0.26}, {'end': 1250.27, 'text': "What's the next thing? Space optimization.", 'start': 1248.469, 'duration': 1.801}, {'end': 1251.491, 'text': 'And can you do this?', 'start': 1250.811, 'duration': 0.68}, {'end': 1259.519, 'text': "Obviously, I've already stated if you see something like index minus one and index, you can always space optimize by using couple of stuffs,", 'start': 1251.792, 'duration': 7.727}, {'end': 1260.86, 'text': 'which is yes.', 'start': 1259.519, 'duration': 1.341}, {'end': 1266.665, 'text': "only storing two rows, and if you, if you're not understanding this, it's your fault.", 'start': 1262.023, 'duration': 4.642}], 'summary': 'Testing and submission are successful. next task: space optimization by storing only two rows.', 'duration': 29.032, 'max_score': 1237.633, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk1237633.jpg'}, {'end': 1327.952, 'src': 'embed', 'start': 1309.664, 'weight': 2, 'content': [{'end': 1312.125, 'text': 'oh, we again did the same mistake of long.', 'start': 1309.664, 'duration': 2.461}, {'end': 1314.646, 'text': 'just make sure this is long, long and now try to submit this.', 'start': 1312.125, 'duration': 2.521}, {'end': 1320.629, 'text': 'so, guys, i hope you have understood the recursion, the memation, the tabulation, the space optimization approach, just in case you did, please,', 'start': 1314.646, 'duration': 5.983}, {'end': 1324.751, 'text': "please, please make sure you like this video and if you're new to this channel, please do consider subscribing.", 'start': 1320.629, 'duration': 4.122}, {'end': 1326.792, 'text': "and yeah, with this i'll be wrapping up this video.", 'start': 1324.751, 'duration': 2.041}, {'end': 1327.952, 'text': "let's meet in the next one, till then, bye.", 'start': 1326.792, 'duration': 1.16}], 'summary': 'Explanation of recursion, memoization, tabulation, and space optimization. encourages viewers to like and subscribe.', 'duration': 18.288, 'max_score': 1309.664, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk1309664.jpg'}], 'start': 1164.574, 'title': 'Implementing dynamic programming', 'summary': 'Emphasizes implementing dynamic programming with space optimization for a specific problem, highlighting the iterative approach, careful variable management, and swapping. the speaker encourages engagement through likes and subscriptions.', 'chapters': [{'end': 1327.952, 'start': 1164.574, 'title': 'Dynamic programming space optimization', 'summary': 'Highlights the process of implementing dynamic programming with space optimization for a specific problem, emphasizing the iterative approach and the need for careful variable management and swapping. the speaker also urges viewers to engage with the content through likes and subscriptions.', 'duration': 163.378, 'highlights': ['The speaker emphasizes the process of implementing dynamic programming with space optimization for a specific problem, focusing on iterative variable management and swapping.', 'The speaker urges viewers to engage with the content through likes and subscriptions to the channel.', 'The chapter provides a detailed walkthrough of implementing dynamic programming with space optimization, including the iterative approach and variable management.', 'The speaker highlights the importance of understanding recursion, memoization, tabulation, and space optimization approaches in dynamic programming.']}], 'duration': 163.378, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/HgyouUi11zk/pics/HgyouUi11zk1164574.jpg', 'highlights': ['The chapter provides a detailed walkthrough of implementing dynamic programming with space optimization, including the iterative approach and variable management.', 'The speaker emphasizes the process of implementing dynamic programming with space optimization for a specific problem, focusing on iterative variable management and swapping.', 'The speaker highlights the importance of understanding recursion, memoization, tabulation, and space optimization approaches in dynamic programming.', 'The speaker urges viewers to engage with the content through likes and subscriptions to the channel.']}], 'highlights': ['The process of tabulation and recursion in solving the index and target problem is described, focusing on the bottom-up recursion technique, moving from n-1 till 0 and t to 0, to easily solve the problem.', 'The chapter provides a detailed walkthrough of implementing dynamic programming with space optimization, including the iterative approach and variable management.', 'The approach involves using dynamic programming to determine the number of ways to make a coin change, allowing for the repetition of elements to form the target.', 'The time complexity of the memoization solution becomes O(n*target) and the space complexity becomes n*target, plus an auxiliary stack space of n*target.', 'The need for memoization to reduce the time complexity is highlighted, as recursion alone results in exponential complexity, making it important to optimize the algorithm.']}