title
DP 14. Subset Sum Equals to Target | Identify DP on Subsequences and Ways to Solve them

description
Lecture Notes/C++/Java Codes: https://takeuforward.org/data-structure/subset-sum-equal-to-target-dp-14/ Problem Link:https://bit.ly/3ukNmRZ 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 subsets sum equal to K. This problem is the first problem on DP on Subsequences Pattern. Please watch this video to have a clear concept of take/notTake concept. 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 14. Subset Sum Equals to Target | Identify DP on Subsequences and Ways to Solve them', 'heatmap': [{'end': 1352.535, 'start': 1234.204, 'weight': 0.897}, {'end': 1537.761, 'start': 1370.697, 'weight': 0.893}], 'summary': 'Covers dynamic programming on subsequences and subsets, explaining the approach of using recursion to generate subsequences, exploring pattern writing recurrences, forming subsequences to achieve a target, optimizing recursion, discussing memoization and tabulation, and demonstrating the implementation of dynamic programming for a specific problem with space optimization.', 'chapters': [{'end': 447.821, 'segs': [{'end': 133.942, 'src': 'embed', 'start': 103.296, 'weight': 0, 'content': [{'end': 108.481, 'text': 'Generally, we will be dealing with problems where we will be said, okay, this is the target.', 'start': 103.296, 'duration': 5.185}, {'end': 113.786, 'text': 'You have to pick elements from the array in order, like they will give some conditions in order to reach that target.', 'start': 108.802, 'duration': 4.984}, {'end': 123.214, 'text': 'So all the problems that relates subsequence, sets and target will be the part of the next pattern we will be solving.', 'start': 114.227, 'duration': 8.987}, {'end': 124.955, 'text': "We'll be solving a bunch of problems.", 'start': 123.434, 'duration': 1.521}, {'end': 133.942, 'text': 'And again, I promise, the moment we finish the last problem in this pattern, you can solve any problem in this given pattern right?', 'start': 125.156, 'duration': 8.786}], 'summary': 'Solving problems related to subsequences, sets, and targets, with the promise of mastering the pattern.', 'duration': 30.646, 'max_score': 103.296, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI103296.jpg'}, {'end': 176.887, 'src': 'embed', 'start': 150.761, 'weight': 2, 'content': [{'end': 157.088, 'text': 'Your task is to check if there exists a subset in an array with a sum equal to k.', 'start': 150.761, 'duration': 6.327}, {'end': 162.574, 'text': 'basically, does any of the elements combine to give you the sum equal to k?', 'start': 157.088, 'duration': 5.486}, {'end': 168.1, 'text': 'so if there exist, you have to return a true, otherwise you need to return a false like.', 'start': 162.574, 'duration': 5.526}, {'end': 172.704, 'text': 'if you see in this example, we have one, two, three, four and k is four.', 'start': 168.1, 'duration': 4.604}, {'end': 176.887, 'text': "i can say if i pick up probably just the four, i'll get the summation four.", 'start': 172.704, 'duration': 4.183}], 'summary': 'Check if subset of array sums up to k. return true if exists, false if not.', 'duration': 26.126, 'max_score': 150.761, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI150761.jpg'}, {'end': 347.743, 'src': 'embed', 'start': 322.67, 'weight': 1, 'content': [{'end': 328.154, 'text': 'Do we have any other parameter? On every index we need to take care of the target that we are looking for.', 'start': 322.67, 'duration': 5.484}, {'end': 331.716, 'text': 'So we can say we definitely have a target that we are looking for.', 'start': 328.654, 'duration': 3.062}, {'end': 339.339, 'text': 'So always remember this, whatever may be the problem on DP, on sub sequences and these subsets and target problems,', 'start': 332.296, 'duration': 7.043}, {'end': 344.341, 'text': 'we will always try to express everything in terms of index and everything in terms of target.', 'start': 339.339, 'duration': 5.002}, {'end': 347.743, 'text': 'Like in grid, it was I and J in sub sequences.', 'start': 344.702, 'duration': 3.041}], 'summary': 'In dynamic programming, express everything in terms of index and target.', 'duration': 25.073, 'max_score': 322.67, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI322670.jpg'}], 'start': 0.669, 'title': 'Dp on subsequences and subsets', 'summary': 'Covers the concept of subsequences and subsets in dynamic programming, focusing on solving problems related to subsets and targets. it explains the approach of using recursion to generate subsequences, while emphasizing the need for an optimized solution and the importance of expressing problems in terms of index and target.', 'chapters': [{'end': 278.706, 'start': 0.669, 'title': 'Dp on subsequences and subsets', 'summary': 'Covers the concept of subsequences and subsets in dynamic programming, focusing on solving problems related to subsets and targets. the first problem involves checking if there exists a subset in an array with a sum equal to k, demonstrating the approach to solve the problem using subsequences and subsets while emphasizing the need for an optimized solution.', 'duration': 278.037, 'highlights': ['The first problem involves checking if there exists a subset in an array with a sum equal to k, demonstrating the approach to solve the problem using subsequences and subsets while emphasizing the need for an optimized solution.', 'The chapter covers the concept of subsequences and subsets in dynamic programming, focusing on solving problems related to subsets and targets.', 'The first thing that comes to my mind is generate all the sub sequences and check if any of them gives a sum of k, emphasizing the need for an optimized solution.']}, {'end': 447.821, 'start': 279.047, 'title': 'Recursion in generating subsequences', 'summary': 'Explains the approach of using recursion to generate subsequences, emphasizing the importance of expressing problems in terms of index and target, and exploring the possibilities of each index while considering the part of the subsequence or not.', 'duration': 168.774, 'highlights': ['The importance of expressing problems in terms of index and target is emphasized, ensuring that every array problem in dynamic programming (DP) will always have an index and a target.', 'The chapter explains the approach of using recursion to generate subsequences, with a focus on exploring the possibilities of each index, considering whether the array of an index is part of the subsequence or not.', 'The concept of exploring possibilities of each index, including whether the array of an index is part of the subsequence or not, is thoroughly discussed as a crucial step in the recursive method of generating subsequences.']}], 'duration': 447.152, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI669.jpg', 'highlights': ['The chapter covers the concept of subsequences and subsets in dynamic programming, focusing on solving problems related to subsets and targets.', 'The importance of expressing problems in terms of index and target is emphasized, ensuring that every array problem in dynamic programming (DP) will always have an index and a target.', 'The first problem involves checking if there exists a subset in an array with a sum equal to k, demonstrating the approach to solve the problem using subsequences and subsets while emphasizing the need for an optimized solution.']}, {'end': 675.928, 'segs': [{'end': 479.485, 'src': 'embed', 'start': 447.861, 'weight': 1, 'content': [{'end': 449.703, 'text': 'How do I start with target??', 'start': 447.861, 'duration': 1.842}, {'end': 453.006, 'text': 'Now, always remember, what am I looking for?', 'start': 450.283, 'duration': 2.723}, {'end': 454.787, 'text': "I'm looking for the entire array.", 'start': 453.466, 'duration': 1.321}, {'end': 459.271, 'text': 'And if there exists a subsequence with the target, whatever is given to you.', 'start': 455.368, 'duration': 3.903}, {'end': 468.678, 'text': "So I'll try to express it in terms of f of n minus 1, saying in the entire array till index n minus one.", 'start': 460.132, 'duration': 8.546}, {'end': 472.801, 'text': 'hear me out properly, in the entire array till the index n minus one.', 'start': 468.678, 'duration': 4.123}, {'end': 479.485, 'text': 'i repeat again in the entire array till the index n minus one, does there exist a target?', 'start': 472.801, 'duration': 6.684}], 'summary': 'Finding subsequence in array based on target using recursive function.', 'duration': 31.624, 'max_score': 447.861, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI447861.jpg'}, {'end': 518.801, 'src': 'embed', 'start': 498.036, 'weight': 5, 'content': [{'end': 507.658, 'text': "that means I'm doing the indexing zero, one, two, three, and I'm asking on this portion, on this entire array, does there exist someone with a target?", 'start': 498.036, 'duration': 9.622}, {'end': 509.059, 'text': "four?. That's what I'm looking for.", 'start': 507.658, 'duration': 1.401}, {'end': 511.459, 'text': "That's the meaning of f of n minus one target.", 'start': 509.359, 'duration': 2.1}, {'end': 516.539, 'text': 'And this is going to be valid throughout all the DP on subsequences pattern.', 'start': 511.879, 'duration': 4.66}, {'end': 518.801, 'text': 'Okay, so we have understood this.', 'start': 516.94, 'duration': 1.861}], 'summary': 'Explaining the indexing and target in dp subsequences pattern.', 'duration': 20.765, 'max_score': 498.036, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI498036.jpg'}, {'end': 615.931, 'src': 'embed', 'start': 566.493, 'weight': 0, 'content': [{'end': 574.343, 'text': "so i'll be like, if at any moment the target becomes zero, i'll return a true why?", 'start': 566.493, 'duration': 7.85}, {'end': 579.387, 'text': 'because we were looking for a subsequence which gives me the target as zero.', 'start': 574.343, 'duration': 5.044}, {'end': 580.568, 'text': "so i've written that.", 'start': 579.387, 'duration': 1.181}, {'end': 582.57, 'text': 'so we have written the base case for target.', 'start': 580.568, 'duration': 2.002}, {'end': 585.382, 'text': 'What about the other one index??', 'start': 583.7, 'duration': 1.682}, {'end': 589.707, 'text': 'So where is the call starting from? N minus one?', 'start': 586.083, 'duration': 3.624}, {'end': 596.655, 'text': "And we know we will go till the zeroth index, because in an array, it's from n minus oneth index till the zeroth index.", 'start': 590.288, 'duration': 6.367}, {'end': 603.022, 'text': "So, if you're standing at an index zero and you have a certain target value, assume four.", 'start': 597.115, 'duration': 5.907}, {'end': 607.245, 'text': 'Can this target be achieved at this index 0?', 'start': 603.883, 'duration': 3.362}, {'end': 608.306, 'text': 'How can you determine??', 'start': 607.245, 'duration': 1.061}, {'end': 609.687, 'text': 'You can be striper.', 'start': 608.826, 'duration': 0.861}, {'end': 615.931, 'text': 'If the array of 0 contains the value 4, then this target can be achieved, otherwise not.', 'start': 610.327, 'duration': 5.604}], 'summary': 'Explaining target value determination with array indexes and values.', 'duration': 49.438, 'max_score': 566.493, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI566493.jpg'}, {'end': 675.928, 'src': 'embed', 'start': 649.69, 'weight': 4, 'content': [{'end': 656.355, 'text': 'perfect. so first step express and write the base cases is completed.', 'start': 649.69, 'duration': 6.665}, {'end': 662.819, 'text': "always, if you're writing a base case, first think about the target, then think about the index.", 'start': 656.355, 'duration': 6.464}, {'end': 664.36, 'text': 'think about the states.', 'start': 662.819, 'duration': 1.541}, {'end': 667.382, 'text': 'what can be the ultimates of states?', 'start': 664.36, 'duration': 3.022}, {'end': 668.783, 'text': "what's the next thing?", 'start': 667.382, 'duration': 1.401}, {'end': 670.465, 'text': "okay, so what's the next thing?", 'start': 668.783, 'duration': 1.682}, {'end': 675.928, 'text': "explore possibilities of that index, because as of now, you're standing at an index.", 'start': 670.465, 'duration': 5.463}], 'summary': 'Express and write base cases, consider targets and states, explore possibilities.', 'duration': 26.238, 'max_score': 649.69, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI649690.jpg'}], 'start': 447.861, 'title': 'Dp subsequences pattern and writing recurrence', 'summary': 'Explains the dp subsequences pattern and writing recurrences for dynamic programming problems, highlighting the search for a target within an entire array, determining base cases, and exploring possibilities at a given index.', 'chapters': [{'end': 518.801, 'start': 447.861, 'title': 'Dp subsequences pattern', 'summary': 'Explains the dp subsequences pattern, emphasizing the search for a target within an entire array till index n minus one, and the validity of this approach throughout all dp on subsequences patterns.', 'duration': 70.94, 'highlights': ['The meaning of f of n minus one target is to determine if there exists a target in the entire array till the index n minus one, which is applicable to all DP on subsequences patterns.', 'Emphasis on searching for a target within the entire array till index n minus one, using the example of array [1, 2, 3, 4] and target 4, demonstrating the indexing approach and the objective of the search.', 'Explanation of the concept of searching for a target within the entire array till index n minus one, with the example of using f of three, comma four to determine the existence of the target 4 within the given array.']}, {'end': 675.928, 'start': 520.097, 'title': 'Writing recurrence and base cases', 'summary': 'Explains writing recurrences and base cases for a dynamic programming problem, emphasizing on determining base cases for the target and index, and exploring possibilities at a given index.', 'duration': 155.831, 'highlights': ['Base case for the target: If the target becomes zero at any moment, return true as we were looking for a subsequence that gives a target of zero.', 'Determining base case for index 0: If the array at index 0 contains the target value, then the target can be achieved at this index.', 'Emphasizing on exploring possibilities at a given index and determining the ultimates of states for dynamic programming problems.']}], 'duration': 228.067, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI447861.jpg', 'highlights': ['Emphasis on searching for a target within the entire array till index n minus one, using the example of array [1, 2, 3, 4] and target 4, demonstrating the indexing approach and the objective of the search.', 'Explanation of the concept of searching for a target within the entire array till index n minus one, with the example of using f of three, comma four to determine the existence of the target 4 within the given array.', 'Base case for the target: If the target becomes zero at any moment, return true as we were looking for a subsequence that gives a target of zero.', 'Determining base case for index 0: If the array at index 0 contains the target value, then the target can be achieved at this index.', 'Emphasizing on exploring possibilities at a given index and determining the ultimates of states for dynamic programming problems.', 'The meaning of f of n minus one target is to determine if there exists a target in the entire array till the index n minus one, which is applicable to all DP on subsequences patterns.']}, {'end': 918.655, 'segs': [{'end': 704.352, 'src': 'embed', 'start': 675.928, 'weight': 1, 'content': [{'end': 683.215, 'text': "so you are at an index and they're asking can i form a subsequence from zero to that index?", 'start': 675.928, 'duration': 7.287}, {'end': 684.436, 'text': 'that gives me the target.', 'start': 683.215, 'duration': 1.221}, {'end': 691.284, 'text': "Can I form, can I form a subsequence from zero to index that gives me a target? I'll be like, okay, there are two ways.", 'start': 684.916, 'duration': 6.368}, {'end': 696.79, 'text': 'One of the ways is I say, I will not take it.', 'start': 692.325, 'duration': 4.465}, {'end': 704.352, 'text': "So can I say if I don't take it? Yes, can I say if I don't take it, then the function will be, okay, I'm not taking that.", 'start': 698.43, 'duration': 5.922}], 'summary': 'Discussing subsequence formation at index for target calculation.', 'duration': 28.424, 'max_score': 675.928, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI675928.jpg'}, {'end': 800.937, 'src': 'embed', 'start': 724.417, 'weight': 0, 'content': [{'end': 727.139, 'text': "You said hey, listen, I'm not gonna pick this element.", 'start': 724.417, 'duration': 2.722}, {'end': 735.103, 'text': 'Thereby I reduce it to this index minus one and I say from zero to index minus one.', 'start': 727.859, 'duration': 7.244}, {'end': 735.924, 'text': 'can I form the target??', 'start': 735.103, 'duration': 0.821}, {'end': 738.105, 'text': "Because I'm not interested in taking this.", 'start': 736.444, 'duration': 1.661}, {'end': 745.61, 'text': 'So I reduce it and I say, okay, can I form this target now in the reduced portion of the array? I do a search on the reduced portion of the array.', 'start': 738.926, 'duration': 6.684}, {'end': 746.91, 'text': "That's what this means.", 'start': 746.07, 'duration': 0.84}, {'end': 749.292, 'text': 'Make sense? It does.', 'start': 747.431, 'duration': 1.861}, {'end': 752.834, 'text': "Okay, what's the other case? Boolean T.", 'start': 749.852, 'duration': 2.982}, {'end': 759.345, 'text': "Let's keep the take as a true, sorry, initially false, I'll tell you why.", 'start': 755.342, 'duration': 4.003}, {'end': 762.387, 'text': 'When can you take an element into that?', 'start': 760.266, 'duration': 2.121}, {'end': 764.709, 'text': "Now, if you're looking for a target.", 'start': 762.687, 'duration': 2.022}, {'end': 772.034, 'text': "if you're looking for a target, that target has to be greater than equal to that current index.", 'start': 764.709, 'duration': 7.325}, {'end': 775.957, 'text': 'Otherwise, how can you take it into the subsequence?', 'start': 773.095, 'duration': 2.862}, {'end': 786.293, 'text': "Like, for an example, if your array is something like one, three, six and your target is something like two, You can't take six or three,", 'start': 776.478, 'duration': 9.815}, {'end': 789.454, 'text': "can you? In the subsequence, because you're looking for something as two.", 'start': 786.293, 'duration': 3.161}, {'end': 795.435, 'text': "So I'm saying the target is greater than the array index, then only take it, otherwise not.", 'start': 789.974, 'duration': 5.461}, {'end': 800.937, 'text': 'So if I take it, if I take it, I will move to the previous index.', 'start': 795.996, 'duration': 4.941}], 'summary': 'Explanation of conditions for forming a target in a reduced array.', 'duration': 76.52, 'max_score': 724.417, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI724417.jpg'}], 'start': 675.928, 'title': 'Subsequence formation and target check', 'summary': 'Explores the logic of forming a subsequence to achieve a target by iteratively checking the possibility of forming the target with reduced portions of the array. it also discusses the condition for taking an element into a subsequence based on whether the target is greater than or equal to the current index, with a recursive approach to check if a subsequence with a specific target can be achieved.', 'chapters': [{'end': 746.91, 'start': 675.928, 'title': 'Subsequence formation logic', 'summary': 'Explores the logic of forming a subsequence to achieve a target by iteratively checking the possibility of forming the target with reduced portions of the array.', 'duration': 70.982, 'highlights': ['Iterative approach of reducing the array by not taking an element and checking if the target can still be formed, signifying the logic of forming a subsequence. (Relevance: 5)', 'The process involves continuously reducing the index and checking for the possibility of forming the target, demonstrating the iterative nature of subsequence formation. (Relevance: 4)', 'The concept involves checking if a subsequence can be formed from zero to a particular index to achieve the target, emphasizing the iterative exploration of subsequence formation. (Relevance: 3)']}, {'end': 918.655, 'start': 747.431, 'title': 'Subsequence target check', 'summary': 'Discusses the condition for taking an element into a subsequence based on whether the target is greater than or equal to the current index, with a recursive approach to check if a subsequence with a specific target can be achieved.', 'duration': 171.224, 'highlights': ['The condition for taking an element into a subsequence is that the target must be greater than or equal to the current index, illustrated with an example of an array and target value.', 'The recursive approach involves checking if a subsequence with a specific target can be achieved by considering whether a particular array index is part of the subsequence and adjusting the target accordingly.', 'The recursive approach explores two possible choices - to take or not to take an element into the subsequence - and returns true if either choice leads to the target being achieved.']}], 'duration': 242.727, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI675928.jpg', 'highlights': ['Iterative approach of reducing the array by not taking an element and checking if the target can still be formed, signifying the logic of forming a subsequence. (Relevance: 5)', 'The process involves continuously reducing the index and checking for the possibility of forming the target, demonstrating the iterative nature of subsequence formation. (Relevance: 4)', 'The concept involves checking if a subsequence can be formed from zero to a particular index to achieve the target, emphasizing the iterative exploration of subsequence formation. (Relevance: 3)', 'The condition for taking an element into a subsequence is that the target must be greater than or equal to the current index, illustrated with an example of an array and target value.', 'The recursive approach involves checking if a subsequence with a specific target can be achieved by considering whether a particular array index is part of the subsequence and adjusting the target accordingly.', 'The recursive approach explores two possible choices - to take or not to take an element into the subsequence - and returns true if either choice leads to the target being achieved.']}, {'end': 1220.855, 'segs': [{'end': 945.391, 'src': 'embed', 'start': 919.175, 'weight': 3, 'content': [{'end': 923.756, 'text': "And that's how your recurrence will look like in all the subsequence problem.", 'start': 919.175, 'duration': 4.581}, {'end': 926.036, 'text': 'Not take and take.', 'start': 924.136, 'duration': 1.9}, {'end': 929.677, 'text': 'Not take and take all the subsequence problem.', 'start': 926.876, 'duration': 2.801}, {'end': 930.797, 'text': 'You will be seeing that.', 'start': 930.077, 'duration': 0.72}, {'end': 934.14, 'text': 'So, in order to understand this recursion better,', 'start': 931.738, 'duration': 2.402}, {'end': 941.467, 'text': "let's do the recursion tree in the records that we have written so that you also try to see the overlapping sub-problems, if there are any,", 'start': 934.14, 'duration': 7.327}, {'end': 945.391, 'text': 'and then probably we can figure out if this recursion can be optimized or something else.', 'start': 941.467, 'duration': 3.924}], 'summary': 'Recurrence in subsequence problem explained with recursion tree and optimization considerations.', 'duration': 26.216, 'max_score': 919.175, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI919175.jpg'}, {'end': 1134.864, 'src': 'embed', 'start': 1107.334, 'weight': 2, 'content': [{'end': 1111.995, 'text': 'Now this f of two, three, yes, this f of two, three, sees that this is giving him true.', 'start': 1107.334, 'duration': 4.661}, {'end': 1116.896, 'text': 'And you can solve this f of one, three, but the moment it gets one true, it returns.', 'start': 1112.755, 'duration': 4.141}, {'end': 1120.436, 'text': 'Again, you can solve this, but there is no requirement of solving this.', 'start': 1117.376, 'duration': 3.06}, {'end': 1123.797, 'text': "Since you've got a true over here, this can also return a true.", 'start': 1120.916, 'duration': 2.881}, {'end': 1127.378, 'text': 'Now you might ask, Striva, where are the overlapping sub-problems?', 'start': 1124.337, 'duration': 3.041}, {'end': 1134.864, 'text': 'So if I would have gone deep, you would have seen, like in this case, it would have gone by taking.', 'start': 1127.738, 'duration': 7.126}], 'summary': 'The function returns true for specific inputs, highlighting the presence of overlapping sub-problems.', 'duration': 27.53, 'max_score': 1107.334, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI1107334.jpg'}, {'end': 1193.071, 'src': 'embed', 'start': 1149.09, 'weight': 0, 'content': [{'end': 1153.492, 'text': 'so you saw how the recursion did work by taking and non-taking.', 'start': 1149.09, 'duration': 4.402}, {'end': 1158.636, 'text': 'so if we talk about the recursion or time complexity, What will be the recursion time complexity??', 'start': 1153.492, 'duration': 5.144}, {'end': 1165.444, 'text': 'It will be we go of 2 to the power n, because for every array element you have couple of options.', 'start': 1159.417, 'duration': 6.027}, {'end': 1170.069, 'text': "Either you take that element into consideration or you say I'm not going to take this element.", 'start': 1166.005, 'duration': 4.064}, {'end': 1172.152, 'text': 'So you just have couple of considerations.', 'start': 1170.39, 'duration': 1.762}, {'end': 1173.954, 'text': 'So 2 to the power n.', 'start': 1172.592, 'duration': 1.362}, {'end': 1178.238, 'text': 'Space complexity is auxiliary stack space of big orphan.', 'start': 1173.954, 'duration': 4.284}, {'end': 1182.322, 'text': 'now we saw that there were overlapping sub problems.', 'start': 1178.238, 'duration': 4.084}, {'end': 1186.486, 'text': 'yes, we saw that there were overlapping sub problems.', 'start': 1182.322, 'duration': 4.164}, {'end': 1188.207, 'text': 'and how did we saw that?', 'start': 1186.486, 'duration': 1.721}, {'end': 1190.349, 'text': 'if you remember, we started with a very big problem.', 'start': 1188.207, 'duration': 2.142}, {'end': 1193.071, 'text': "we've started with the entire array.", 'start': 1191.01, 'duration': 2.061}], 'summary': 'Recursion time complexity is o(2^n) with overlapping subproblems.', 'duration': 43.981, 'max_score': 1149.09, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI1149090.jpg'}], 'start': 919.175, 'title': 'Recursion in subsequence problem and time complexity', 'summary': 'Discusses recursion in subsequence problem and time complexity, aiming to optimize recursion and highlighting the time complexity of 2 to the power of n and the space complexity of auxiliary stack space of big o(n), with the presence of overlapping sub-problems and the application of memoization.', 'chapters': [{'end': 1026.782, 'start': 919.175, 'title': 'Recursion in subsequence problem', 'summary': 'Discusses the recursion in subsequence problem, where a target value is to be found in an array by considering both taking and not taking elements, aiming to optimize the recursion. it also demonstrates the process through a detailed example.', 'duration': 107.607, 'highlights': ['The recursion in subsequence problem involves considering both taking and not taking elements to find a target value in an array, aiming to optimize the recursion and identify overlapping sub-problems.', 'The detailed example demonstrates the process of recursion in a specific scenario, illustrating the reduction of array elements and target values through the take and not take decisions.']}, {'end': 1220.855, 'start': 1027.603, 'title': 'Recursion and time complexity', 'summary': 'Discusses the concept of recursion and time complexity in solving problems, demonstrating how the time complexity is 2 to the power of n and the space complexity is auxiliary stack space of big o(n), while also highlighting the presence of overlapping sub-problems and the application of memoization.', 'duration': 193.252, 'highlights': ['The recursion time complexity is 2 to the power n because for every array element you have a couple of options, resulting in 2 to the power n considerations.', 'The space complexity is auxiliary stack space of big O(n), as demonstrated by the process of breaking down the problem into subproblems and eventually solving it with a single base case.', 'The presence of overlapping sub-problems is emphasized, demonstrating how breaking down the problem into subproblems results in repetition, thus allowing the application of memoization.']}], 'duration': 301.68, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI919175.jpg', 'highlights': ['The recursion time complexity is 2 to the power n', 'The space complexity is auxiliary stack space of big O(n)', 'The presence of overlapping sub-problems is emphasized', 'The recursion in subsequence problem involves considering both taking and not taking elements', 'The detailed example demonstrates the process of recursion in a specific scenario']}, {'end': 1700.14, 'segs': [{'end': 1352.535, 'src': 'heatmap', 'start': 1220.855, 'weight': 0, 'content': [{'end': 1222.399, 'text': "now let's think about the memoiation.", 'start': 1220.855, 'duration': 1.544}, {'end': 1224.459, 'text': 'What did I say?', 'start': 1223.919, 'duration': 0.54}, {'end': 1225.88, 'text': 'How will you apply memo hash?', 'start': 1224.779, 'duration': 1.101}, {'end': 1229.422, 'text': 'The first trick is figure out the changing states.', 'start': 1226.38, 'duration': 3.042}, {'end': 1233.664, 'text': 'So there is an index and there is a target that might change.', 'start': 1230.042, 'duration': 3.622}, {'end': 1236.966, 'text': 'There is an index and there is a target that might change.', 'start': 1234.204, 'duration': 2.762}, {'end': 1242.449, 'text': 'So, assuming the constraint says target will be lesser than 10 to the power.', 'start': 1237.486, 'duration': 4.963}, {'end': 1248.171, 'text': 'three, assuming the constraint says this and assuming this is also something like this the constraints.', 'start': 1242.449, 'duration': 5.722}, {'end': 1252.254, 'text': 'So index you will take as 10 to the power three plus one.', 'start': 1248.832, 'duration': 3.422}, {'end': 1256.396, 'text': 'one more, because there is something as 10 to the power 3.', 'start': 1253.374, 'duration': 3.022}, {'end': 1262.559, 'text': 'so in order to have this as an index, you need to plus 1, multiply with a target of 10 to the power 3, plus 1.', 'start': 1256.396, 'duration': 6.163}, {'end': 1266.602, 'text': 'so this is the dp array that you will be requiring, and you know how to memorize.', 'start': 1262.559, 'duration': 4.043}, {'end': 1271.685, 'text': 'i have already taught you that, by the way, this will be a boolean dp array.', 'start': 1266.602, 'duration': 5.083}, {'end': 1277.468, 'text': 'this can be a boolean dp array because the function is boolean, or you just need to return a true or false.', 'start': 1271.685, 'duration': 5.783}, {'end': 1282.371, 'text': 'so what i can say is okay, dp of index target.', 'start': 1277.468, 'duration': 4.903}, {'end': 1294.766, 'text': "and if dp of index target is not equal to, by the way, uh, boolean, you can't take.", 'start': 1284.958, 'duration': 9.808}, {'end': 1301.672, 'text': "you have to take true and false, so minus one and return dp of index target, so you can't take.", 'start': 1294.766, 'duration': 6.906}, {'end': 1306.404, 'text': "uh, You can't take true and false in the memoization.", 'start': 1301.672, 'duration': 4.732}, {'end': 1308.864, 'text': "So you can't take Boolean, you have to take an integer.", 'start': 1306.944, 'duration': 1.92}, {'end': 1311.705, 'text': 'For memoization in tabulation, you can take true and false.', 'start': 1309.225, 'duration': 2.48}, {'end': 1317.787, 'text': 'Why? Because, you know, minus one is marked for any unvisited state.', 'start': 1312.525, 'duration': 5.262}, {'end': 1323.328, 'text': "So how will you determine if you mark true and false for the unvisited state? So it's very important minus one is marked.", 'start': 1317.907, 'duration': 5.421}, {'end': 1325.889, 'text': 'This is how the memoization solution will do.', 'start': 1324.328, 'duration': 1.561}, {'end': 1327.969, 'text': 'And the memoization solution is very simple.', 'start': 1326.389, 'duration': 1.58}, {'end': 1331.31, 'text': 'Time complexity will be N crossed target.', 'start': 1328.569, 'duration': 2.741}, {'end': 1340.484, 'text': 'the space complexity will be n cross the target array, and an auxiliary space of bico of n,', 'start': 1333.678, 'duration': 6.806}, {'end': 1344.528, 'text': 'which is an auxiliary space complexity which we have to reduce.', 'start': 1340.484, 'duration': 4.044}, {'end': 1347.07, 'text': 'that can only be done by tabulation.', 'start': 1344.528, 'duration': 2.542}, {'end': 1349.052, 'text': 'so the next step is tabulation.', 'start': 1347.07, 'duration': 1.982}, {'end': 1350.673, 'text': "let's quickly check that out.", 'start': 1349.052, 'duration': 1.621}, {'end': 1352.535, 'text': 'so how do you write the tabulation?', 'start': 1350.673, 'duration': 1.862}], 'summary': 'Memoization solution for dynamic programming with time complexity n*target and space complexity n*target.', 'duration': 61.516, 'max_score': 1220.855, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI1220855.jpg'}, {'end': 1361.249, 'src': 'embed', 'start': 1333.678, 'weight': 4, 'content': [{'end': 1340.484, 'text': 'the space complexity will be n cross the target array, and an auxiliary space of bico of n,', 'start': 1333.678, 'duration': 6.806}, {'end': 1344.528, 'text': 'which is an auxiliary space complexity which we have to reduce.', 'start': 1340.484, 'duration': 4.044}, {'end': 1347.07, 'text': 'that can only be done by tabulation.', 'start': 1344.528, 'duration': 2.542}, {'end': 1349.052, 'text': 'so the next step is tabulation.', 'start': 1347.07, 'duration': 1.982}, {'end': 1350.673, 'text': "let's quickly check that out.", 'start': 1349.052, 'duration': 1.621}, {'end': 1352.535, 'text': 'so how do you write the tabulation?', 'start': 1350.673, 'duration': 1.862}, {'end': 1354.517, 'text': "i've already taught you the steps.", 'start': 1352.535, 'duration': 1.982}, {'end': 1355.698, 'text': 'how do you write the tabulation, guys?', 'start': 1354.517, 'duration': 1.181}, {'end': 1361.249, 'text': 'First step is declare the DP array of the same size, N and target.', 'start': 1356.906, 'duration': 4.343}], 'summary': 'Space complexity is n * target array, with auxiliary space of o(n). tabulation is the next step to reduce auxiliary space.', 'duration': 27.571, 'max_score': 1333.678, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI1333678.jpg'}, {'end': 1553.13, 'src': 'heatmap', 'start': 1370.697, 'weight': 1, 'content': [{'end': 1375.86, 'text': 'So just without thinking anything, go to the recurrence and see what are the base cases.', 'start': 1370.697, 'duration': 5.163}, {'end': 1380.384, 'text': 'The recurrence says any moment the target is zero.', 'start': 1376.981, 'duration': 3.403}, {'end': 1383.146, 'text': 'Any moment the target is zero, you return true.', 'start': 1381.124, 'duration': 2.022}, {'end': 1387.645, 'text': 'So, if target is zero, what can be the possible value of index?', 'start': 1384.844, 'duration': 2.801}, {'end': 1391.507, 'text': 'Ask your brain, ask your brain, what can be the possible values of index?', 'start': 1388.366, 'duration': 3.141}, {'end': 1394.229, 'text': 'Zero one, two till n, minus one.', 'start': 1392.188, 'duration': 2.041}, {'end': 1398.09, 'text': 'So for every one on zeroth index, you return a true.', 'start': 1394.769, 'duration': 3.321}, {'end': 1399.231, 'text': 'So just write it.', 'start': 1398.611, 'duration': 0.62}, {'end': 1401.032, 'text': "Don't think anything else.", 'start': 1399.751, 'duration': 1.281}, {'end': 1401.752, 'text': 'Just go and write.', 'start': 1401.112, 'duration': 0.64}, {'end': 1405.154, 'text': 'Tabulation, you should not complicate.', 'start': 1403.313, 'duration': 1.841}, {'end': 1406.074, 'text': 'You should keep it simple.', 'start': 1405.274, 'duration': 0.8}, {'end': 1411.077, 'text': 'For i equal to zero till n minus one, you write dp of.', 'start': 1406.635, 'duration': 4.442}, {'end': 1414.609, 'text': 'I target is 0 equal to true.', 'start': 1412.328, 'duration': 2.281}, {'end': 1420.31, 'text': "That's what you did write in the base case because for every index, if target is 0, you write true.", 'start': 1416.009, 'duration': 4.301}, {'end': 1421.37, 'text': 'So just write it now.', 'start': 1420.59, 'duration': 0.78}, {'end': 1425.431, 'text': "What are you waiting for? Let's look at the next base case.", 'start': 1421.67, 'duration': 3.761}, {'end': 1429.992, 'text': 'The next base case says if index is 0.', 'start': 1426.491, 'duration': 3.501}, {'end': 1431.453, 'text': 'So index is 0 for sure.', 'start': 1429.992, 'duration': 1.461}, {'end': 1436.374, 'text': "Return true if it's equivalent to target.", 'start': 1433.253, 'duration': 3.121}, {'end': 1440.975, 'text': 'So index is 0 and target can be anything.', 'start': 1437.914, 'duration': 3.061}, {'end': 1446.706, 'text': 'okay, but when will it be true?', 'start': 1443.464, 'duration': 3.242}, {'end': 1450.929, 'text': 'when will it be true for every target?', 'start': 1446.706, 'duration': 4.223}, {'end': 1454.191, 'text': 'what can be the possible values of target at index?', 'start': 1450.929, 'duration': 3.262}, {'end': 1457.472, 'text': 'zero, think, think, ask your brain to think.', 'start': 1454.191, 'duration': 3.281}, {'end': 1458.113, 'text': "you'll be like.", 'start': 1457.472, 'duration': 0.641}, {'end': 1459.554, 'text': 'it can be anything.', 'start': 1458.113, 'duration': 1.441}, {'end': 1460.534, 'text': 'target can be zero.', 'start': 1459.554, 'duration': 0.98}, {'end': 1461.855, 'text': 'target can be one.', 'start': 1460.534, 'duration': 1.321}, {'end': 1463.316, 'text': "it can't be zero, but it can be one.", 'start': 1461.855, 'duration': 1.461}, {'end': 1464.597, 'text': 'it can be two.', 'start': 1463.316, 'duration': 1.281}, {'end': 1470.06, 'text': 'it can be till any value of target, the given target.', 'start': 1464.597, 'duration': 5.463}, {'end': 1470.7, 'text': "so you'll be like.", 'start': 1470.06, 'duration': 0.64}, {'end': 1473.062, 'text': 'but but Which guy will be true?', 'start': 1470.7, 'duration': 2.362}, {'end': 1475.403, 'text': 'Only A of 0 will be true.', 'start': 1473.802, 'duration': 1.601}, {'end': 1480.824, 'text': 'In DP of 0, A of 0 will only be true.', 'start': 1476.403, 'duration': 4.421}, {'end': 1488.145, 'text': "Realize no matter what the target is, no matter what the target is, if it's equal to A of 0, then only it will be true.", 'start': 1481.404, 'duration': 6.741}, {'end': 1490.085, 'text': 'Everyone else will be false.', 'start': 1488.745, 'duration': 1.34}, {'end': 1492.646, 'text': 'So initially you can mark the entire DP as false.', 'start': 1490.566, 'duration': 2.08}, {'end': 1497.647, 'text': 'So can I say only DP of 0 and A of 0 will be true? I can.', 'start': 1493.506, 'duration': 4.141}, {'end': 1507.042, 'text': 'So basically I can be like, okay, the next base cases, if DP of zero area of zero is true.', 'start': 1500.137, 'duration': 6.905}, {'end': 1508.763, 'text': 'Why? Very obvious.', 'start': 1507.082, 'duration': 1.681}, {'end': 1512.725, 'text': "I'm saying at index zero.", 'start': 1509.864, 'duration': 2.861}, {'end': 1514.447, 'text': 'can I form this target a of zero?', 'start': 1512.725, 'duration': 1.722}, {'end': 1520.291, 'text': 'And the answer is yes, because that only on the air of zero array you can form a target day of zero.', 'start': 1514.927, 'duration': 5.364}, {'end': 1521.872, 'text': "You can't form apart from that.", 'start': 1520.451, 'duration': 1.421}, {'end': 1523.813, 'text': 'So this, these are the base cases.', 'start': 1522.272, 'duration': 1.541}, {'end': 1529.637, 'text': 'First step done next step form the nested loops.', 'start': 1524.613, 'duration': 5.024}, {'end': 1534.939, 'text': 'How many states are there? Two states.', 'start': 1531.397, 'duration': 3.542}, {'end': 1537.761, 'text': 'Index will be one.', 'start': 1537.02, 'duration': 0.741}, {'end': 1539.902, 'text': 'The other one will be targeted.', 'start': 1538.861, 'duration': 1.041}, {'end': 1543.844, 'text': 'Where does index start from? Go and look at the recurrence.', 'start': 1540.682, 'duration': 3.162}, {'end': 1550.308, 'text': 'In the recurrence, index was n minus one, n minus two, n minus three, and so on till zero.', 'start': 1544.865, 'duration': 5.443}, {'end': 1553.13, 'text': 'Top down, top down.', 'start': 1550.728, 'duration': 2.402}], 'summary': 'Developing a dynamic programming solution for a problem with base cases and nested loops.', 'duration': 30.858, 'max_score': 1370.697, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI1370697.jpg'}], 'start': 1220.855, 'title': 'Dynamic programming concepts', 'summary': 'Covers memoization for managing changing states like index and target, involving constraints such as ensuring the target is less than 10^3 and adjusting the index accordingly. it also explains dynamic programming basics including memoization and tabulation, emphasizing the importance of base cases and nested loops in formulating the dp array and demonstrating the time and space complexity for both memoization and tabulation.', 'chapters': [{'end': 1262.559, 'start': 1220.855, 'title': 'Memoization for index and target', 'summary': 'Discusses the application of memoization for managing changing states like index and target, involving constraints such as ensuring the target is less than 10^3 and adjusting the index accordingly.', 'duration': 41.704, 'highlights': ['Memoization involves managing changing states like index and target, and ensuring the target is lesser than 10^3.', 'Constraints involve adjusting the index by adding 1 and multiplying it with the target of 10^3 plus 1.']}, {'end': 1700.14, 'start': 1262.559, 'title': 'Dynamic programming basics', 'summary': 'Explains dynamic programming basics including memoization and tabulation. it emphasizes the importance of base cases and nested loops in formulating the dp array and demonstrates the time and space complexity for both memoization and tabulation.', 'duration': 437.581, 'highlights': ['Dynamic programming array is required for memoization and tabulation', 'Importance of base cases and nested loops', 'Time and space complexity for memoization and tabulation']}], 'duration': 479.285, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI1220855.jpg', 'highlights': ['Dynamic programming array is required for memoization and tabulation', 'Importance of base cases and nested loops', 'Memoization involves managing changing states like index and target, and ensuring the target is lesser than 10^3', 'Constraints involve adjusting the index by adding 1 and multiplying it with the target of 10^3 plus 1', 'Time and space complexity for memoization and tabulation']}, {'end': 2319.867, 'segs': [{'end': 2058.277, 'src': 'embed', 'start': 2028.217, 'weight': 4, 'content': [{'end': 2032.2, 'text': 'We can space optimize if we have a state as I minus one.', 'start': 2028.217, 'duration': 3.983}, {'end': 2033.241, 'text': 'because, because, because.', 'start': 2032.2, 'duration': 1.041}, {'end': 2039.666, 'text': 'First time, we always write the index 0.', 'start': 2034.178, 'duration': 5.488}, {'end': 2041.689, 'text': 'We always take the index 0.', 'start': 2039.666, 'duration': 2.023}, {'end': 2045.715, 'text': 'And in this index 0, some a of i will be marked as true.', 'start': 2041.689, 'duration': 4.026}, {'end': 2050.014, 'text': 'then we go to index one, then we compute this.', 'start': 2046.914, 'duration': 3.1}, {'end': 2058.277, 'text': 'But over here, if you carefully observe in the base case, yes, if you carefully observe in the base case, for every index, for every row,', 'start': 2050.675, 'duration': 7.602}], 'summary': 'Optimize space by using state as i minus one, marking a of i as true at index 0.', 'duration': 30.06, 'max_score': 2028.217, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI2028217.jpg'}, {'end': 2234.539, 'src': 'embed', 'start': 2174.63, 'weight': 0, 'content': [{'end': 2175.791, 'text': 'Now we come to index of one.', 'start': 2174.63, 'duration': 1.161}, {'end': 2179.874, 'text': 'What did I tell you? Index of I minus one means previous.', 'start': 2176.332, 'duration': 3.542}, {'end': 2184.238, 'text': 'Index of I minus one means previous.', 'start': 2180.995, 'duration': 3.243}, {'end': 2188.201, 'text': 'DP of index means current.', 'start': 2185.539, 'duration': 2.662}, {'end': 2192.888, 'text': 'Whenever this is completed, The previous is now current.', 'start': 2189.302, 'duration': 3.586}, {'end': 2198.258, 'text': 'And at the end, n-1 is the previous of current.', 'start': 2194.691, 'duration': 3.567}, {'end': 2200.322, 'text': 'Run this off.', 'start': 2199.841, 'duration': 0.481}, {'end': 2201.805, 'text': "Let's quickly run this off.", 'start': 2200.924, 'duration': 0.881}, {'end': 2203.288, 'text': 'Runs fine.', 'start': 2202.807, 'duration': 0.481}, {'end': 2206.714, 'text': 'what is the time complexity?', 'start': 2204.531, 'duration': 2.183}, {'end': 2210.658, 'text': 'now? it still stays the same and into target.', 'start': 2206.714, 'duration': 3.944}, {'end': 2212.7, 'text': 'but what is the space complexity?', 'start': 2210.658, 'duration': 2.042}, {'end': 2217.365, 'text': 'the space complexity has now boiled into just because of target,', 'start': 2212.7, 'duration': 4.665}, {'end': 2226.955, 'text': 'and we are not using any index array just because of target is helping us to solve this problem in just b go of k space.', 'start': 2217.365, 'duration': 9.59}, {'end': 2227.816, 'text': "that's amazing.", 'start': 2226.955, 'duration': 0.861}, {'end': 2229.436, 'text': "we're not requiring a 2d array.", 'start': 2227.816, 'duration': 1.62}, {'end': 2231.317, 'text': 'so remember this concept of previous and k.', 'start': 2229.436, 'duration': 1.881}, {'end': 2232.938, 'text': "whenever you see i minus 1, it's just.", 'start': 2231.317, 'duration': 1.621}, {'end': 2234.539, 'text': 'you need to store the previous row.', 'start': 2232.938, 'duration': 1.601}], 'summary': 'Using target, space complexity is o(k), no 2d array required.', 'duration': 59.909, 'max_score': 2174.63, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI2174630.jpg'}], 'start': 1700.14, 'title': 'Dynamic programming practice and dp on subsequences', 'summary': 'Demonstrates the implementation of dynamic programming for a specific problem, emphasizing the application of memoization and space optimization. it also discusses dynamic programming on subsequences, demonstrating space complexity of o(k) and time complexity of o(n*k) with step-by-step optimization process.', 'chapters': [{'end': 2124.334, 'start': 1700.14, 'title': 'Dynamic programming practice', 'summary': 'Demonstrates the implementation of dynamic programming for a specific problem, emphasizing the application of memoization and space optimization to achieve efficiency.', 'duration': 424.194, 'highlights': ['The function is implemented to solve a problem using dynamic programming, with the emphasis on memoization and space optimization.', 'The importance of base cases and memoization in dynamic programming is emphasized, particularly in the context of space optimization.', 'The concept of marking the zeroth index as true for every row in space optimization is explained, emphasizing the importance of understanding previous and current states in dynamic programming.']}, {'end': 2319.867, 'start': 2124.734, 'title': 'Dp on subsequences', 'summary': 'Discusses dynamic programming on subsequences, emphasizing the concept of storing previous rows to optimize space complexity, resulting in a space complexity of o(k) and a time complexity of o(n*k), with a demonstration of filling the table step by step to understand the optimization process.', 'duration': 195.133, 'highlights': ['The space complexity has now boiled down to just O(K) due to not using any index array, resulting in a space-efficient solution.', 'The concept of storing previous rows is emphasized to optimize space complexity, resulting in a space complexity of O(K).', 'The time complexity remains O(n*K) for the demonstrated algorithm on dynamic programming on subsequences.']}], 'duration': 619.727, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fWX9xDmIzRI/pics/fWX9xDmIzRI1700140.jpg', 'highlights': ['The space complexity has now boiled down to just O(K) due to not using any index array, resulting in a space-efficient solution.', 'The concept of storing previous rows is emphasized to optimize space complexity, resulting in a space complexity of O(K).', 'The time complexity remains O(n*K) for the demonstrated algorithm on dynamic programming on subsequences.', 'The function is implemented to solve a problem using dynamic programming, with the emphasis on memoization and space optimization.', 'The importance of base cases and memoization in dynamic programming is emphasized, particularly in the context of space optimization.', 'The concept of marking the zeroth index as true for every row in space optimization is explained, emphasizing the importance of understanding previous and current states in dynamic programming.']}], 'highlights': ['The space complexity has now boiled down to just O(K) due to not using any index array, resulting in a space-efficient solution.', 'Dynamic programming array is required for memoization and tabulation', 'The importance of expressing problems in terms of index and target is emphasized, ensuring that every array problem in dynamic programming (DP) will always have an index and a target.', 'The concept involves checking if a subsequence can be formed from zero to a particular index to achieve the target, emphasizing the iterative exploration of subsequence formation. (Relevance: 3)', 'The chapter covers the concept of subsequences and subsets in dynamic programming, focusing on solving problems related to subsets and targets.']}