Coursnap

description
Lecture Notes/C++/Java Codes: https://takeuforward.org/data-structure/dynamic-programming-ninjas-training-dp-7/ Problem Link: https://bit.ly/3F4yl8z Pre-req for this Series: https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9 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 are starting with 2D DP. We solve the problem Ninja's Training which teaches you how to think of other parameters apart from index. We also learn space optimization in 2D Dp. 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 7. Ninja's Training | MUST WATCH for 2D CONCEPTS 🔥 | Vacation | Atcoder | 2D DP |", 'heatmap': [{'end': 722.823, 'start': 657.13, 'weight': 0.763}, {'end': 1381.53, 'start': 1284.545, 'weight': 0.851}, {'end': 1445.145, 'start': 1407.433, 'weight': 0.706}, {'end': 1696.393, 'start': 1625.317, 'weight': 0.932}, {'end': 2010.739, 'start': 1850.664, 'weight': 0.849}, {'end': 2636.781, 'start': 2599.444, 'weight': 1}, {'end': 3051.639, 'start': 3007.945, 'weight': 0.849}], 'summary': 'Covers various topics including dynamic programming, greedy algorithms, recursion, and optimization techniques in c++, with practical examples and detailed explanations, emphasizing time and space complexity and practical implementations.', 'chapters': [{'end': 239.142, 'segs': [{'end': 68.749, 'src': 'embed', 'start': 23.121, 'weight': 0, 'content': [{'end': 27.426, 'text': 'So Ninja is planning this 10 days long training schedule.', 'start': 23.121, 'duration': 4.305}, {'end': 31.732, 'text': 'Each day he can perform any one of these three activities.', 'start': 28.127, 'duration': 3.605}, {'end': 35.337, 'text': 'So there are three activities that the Ninja can perform.', 'start': 32.173, 'duration': 3.164}, {'end': 41.543, 'text': 'running, uh, fighting practice or learning new moves i forget about these stuffs.', 'start': 36.3, 'duration': 5.243}, {'end': 44.804, 'text': 'each activity has some merit points on each day.', 'start': 41.543, 'duration': 3.261}, {'end': 46.545, 'text': 'so there are three activities.', 'start': 44.804, 'duration': 1.741}, {'end': 51.067, 'text': 'if you perform any activity on a given day, you get some points.', 'start': 46.545, 'duration': 4.522}, {'end': 57.531, 'text': "now, as ninja has to improve all his skills, he can't do the same activity in two consecutive days.", 'start': 51.067, 'duration': 6.464}, {'end': 63.983, 'text': 'that means if on the first day he has done running, on the second day he again cannot run.', 'start': 58.516, 'duration': 5.467}, {'end': 68.749, 'text': 'so two activities cannot be done on consecutive days.', 'start': 63.983, 'duration': 4.766}], 'summary': 'Ninja plans 10-day training with 3 activities, earning merit points, avoiding consecutive activities.', 'duration': 45.628, 'max_score': 23.121, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog23121.jpg'}, {'end': 117.747, 'src': 'embed', 'start': 91.369, 'weight': 3, 'content': [{'end': 95.092, 'text': "now you're given a 2d array of size n cross 3.", 'start': 91.369, 'duration': 3.723}, {'end': 96.713, 'text': "it's a slightly different one.", 'start': 95.092, 'duration': 1.621}, {'end': 97.854, 'text': 'n cross 3.', 'start': 96.713, 'duration': 1.141}, {'end': 107.376, 'text': 'okay, so basically, uh, there will be three columns and n rows with the points corresponding to each day and activity.', 'start': 97.854, 'duration': 9.522}, {'end': 112.061, 'text': 'your task is to calculate the maximum number of merit points that ninja can earn.', 'start': 107.376, 'duration': 4.685}, {'end': 114.603, 'text': 'so let me just explain you what does this mean?', 'start': 112.061, 'duration': 2.542}, {'end': 117.747, 'text': 'so, basically it means uh, these are the three columns.', 'start': 114.603, 'duration': 3.144}], 'summary': 'Given 2d array of size n x 3, find max merit points for ninja.', 'duration': 26.378, 'max_score': 91.369, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog91369.jpg'}, {'end': 246.089, 'src': 'embed', 'start': 214.501, 'weight': 1, 'content': [{'end': 217.523, 'text': 'you did greedily, but you will fail.', 'start': 214.501, 'duration': 3.022}, {'end': 220.746, 'text': 'why? because since you did greedily, uh, you took 50.', 'start': 217.523, 'duration': 3.223}, {'end': 225.37, 'text': 'you missed out on something which was much bigger in the next step.', 'start': 220.746, 'duration': 4.624}, {'end': 232.896, 'text': "so ideally, better would have been if you'd have taken 10, correct, and then you would have taken 100.", 'start': 225.37, 'duration': 7.526}, {'end': 239.142, 'text': "so if you'd have taken a 10 on the zero day, like you have performed this task, then you would have performed this task.", 'start': 232.896, 'duration': 6.246}, {'end': 246.089, 'text': 'Thereby, the total would have been 110, which is indeed the maximum merit points that you can earn.', 'start': 240.165, 'duration': 5.924}], 'summary': 'Greedily taking 50 instead of 10 resulted in missing out on earning a total of 110 merit points.', 'duration': 31.588, 'max_score': 214.501, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog214501.jpg'}], 'start': 0.209, 'title': 'Dynamic programming and greedy approach', 'summary': "Discusses 'ninja's training' problem in dynamic programming, focusing on planning a 10-day training schedule to maximize merit points. it also explores the greedy approach for optimizing task performance over two days, emphasizing the trade-offs of immediate gains and missed opportunities.", 'chapters': [{'end': 117.747, 'start': 0.209, 'title': "Dynamic programming - ninja's training", 'summary': "Discusses a dynamic programming problem called 'ninja's training' in the seventh lecture of the dynamic programming playlist. it involves planning a 10-day training schedule with three activities, with the goal of maximizing merit points while avoiding consecutive days of the same activity.", 'duration': 117.538, 'highlights': ['Ninja plans a 10-day training schedule with three activities: running, fighting practice, and learning new moves, aiming to maximize merit points.', 'Ninja cannot perform the same activity on two consecutive days, similar to the concept of not picking consecutive numbers.', 'The goal is to calculate the maximum number of merit points that Ninja can earn based on the points corresponding to each day and activity in a 2D array of size n x 3.']}, {'end': 239.142, 'start': 117.747, 'title': 'Optimizing task performance', 'summary': 'Discusses the greedy approach for task performance over two days, aiming to maximize merit points, highlighting the consequence of choosing tasks solely based on immediate gains and the potential for missed opportunities.', 'duration': 121.395, 'highlights': ['The consequence of choosing tasks greedily, such as selecting the task with the immediate maximum reward, can lead to missed opportunities for greater overall merit points.', 'Tasks cannot be performed on consecutive days, limiting the options for task selection and potentially impacting the total merit points collected.', 'Illustrates the scenario where a more strategic approach to task selection, considering future opportunities, can result in a higher total of merit points collected.']}], 'duration': 238.933, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog209.jpg', 'highlights': ['Ninja plans a 10-day training schedule with three activities: running, fighting practice, and learning new moves, aiming to maximize merit points.', 'The consequence of choosing tasks greedily can lead to missed opportunities for greater overall merit points.', 'Ninja cannot perform the same activity on two consecutive days, similar to the concept of not picking consecutive numbers.', 'Illustrates the scenario where a more strategic approach to task selection can result in a higher total of merit points collected.', 'The goal is to calculate the maximum number of merit points that Ninja can earn based on the points corresponding to each day and activity in a 2D array of size n x 3.', 'Tasks cannot be performed on consecutive days, limiting the options for task selection and potentially impacting the total merit points collected.']}, {'end': 1046.247, 'segs': [{'end': 271.635, 'src': 'embed', 'start': 240.165, 'weight': 0, 'content': [{'end': 246.089, 'text': 'Thereby, the total would have been 110, which is indeed the maximum merit points that you can earn.', 'start': 240.165, 'duration': 5.924}, {'end': 247.57, 'text': 'That is what the question states.', 'start': 246.429, 'duration': 1.141}, {'end': 251.072, 'text': 'So, we observed that greedy fails.', 'start': 248.49, 'duration': 2.582}, {'end': 260.538, 'text': 'And whenever greedy fails, you know what you need to do? First thing comes, try all possible ways.', 'start': 251.973, 'duration': 8.565}, {'end': 263.74, 'text': "Yes, you're going to try all possible ways.", 'start': 260.678, 'duration': 3.062}, {'end': 264.241, 'text': "That's the.", 'start': 263.8, 'duration': 0.441}, {'end': 271.635, 'text': "definitely. that's definitely the first thing that comes to my mind, and whenever i say try all possible ways,", 'start': 265.552, 'duration': 6.083}], 'summary': 'Greedy algorithm failed, so try all possible ways to maximize merit points, with a maximum of 110.', 'duration': 31.47, 'max_score': 240.165, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog240165.jpg'}, {'end': 317.255, 'src': 'embed', 'start': 286.763, 'weight': 1, 'content': [{'end': 293.597, 'text': 'step number one express every possible problem in terms of index.', 'start': 286.763, 'duration': 6.834}, {'end': 296.679, 'text': 'second, do stuffs on that index.', 'start': 293.597, 'duration': 3.082}, {'end': 298.26, 'text': 'very, very important.', 'start': 296.679, 'duration': 1.581}, {'end': 299.601, 'text': 'do stuffs on that index.', 'start': 298.26, 'duration': 1.341}, {'end': 305.526, 'text': 'third, according to the question, like over here, the question states find the maximum merit point.', 'start': 299.601, 'duration': 5.925}, {'end': 307.687, 'text': 'so you have to find the max.', 'start': 305.526, 'duration': 2.161}, {'end': 309.028, 'text': 'you have to find the max.', 'start': 307.687, 'duration': 1.341}, {'end': 317.255, 'text': 'so if you follow these three steps, you can definitely write any of the recurrence relationships correct?', 'start': 309.028, 'duration': 8.227}], 'summary': 'Express problems in terms of index, do stuffs, find maximum merit point for correct recurrence relationships.', 'duration': 30.492, 'max_score': 286.763, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog286763.jpg'}, {'end': 589.29, 'src': 'embed', 'start': 555.799, 'weight': 2, 'content': [{'end': 557.4, 'text': "Got it? That's how you think.", 'start': 555.799, 'duration': 1.601}, {'end': 559.581, 'text': "That's how you think of recurrence.", 'start': 558.34, 'duration': 1.241}, {'end': 562.043, 'text': 'So we have assigned, like we have done this.', 'start': 559.941, 'duration': 2.102}, {'end': 563.603, 'text': 'first step.', 'start': 562.643, 'duration': 0.96}, {'end': 569.305, 'text': 'first step is done of recurrence relationships, which is identifying along with index if you need something else.', 'start': 563.603, 'duration': 5.702}, {'end': 570.965, 'text': 'so we identified along with index.', 'start': 569.305, 'duration': 1.66}, {'end': 576.387, 'text': 'we need, uh, sorry, rather, the last day, the last task, whatever you did.', 'start': 570.965, 'duration': 5.422}, {'end': 583.069, 'text': "so, uh, let's, let's keep it quite simple, because we will be having zero based indexing arrays.", 'start': 576.387, 'duration': 6.682}, {'end': 589.29, 'text': "so let's keep it something like uh, task, let's keep the numbers very straightforward.", 'start': 583.069, 'duration': 6.221}], 'summary': 'Introduced first step of recurrence relationships, identifying along with index for zero-based indexing arrays.', 'duration': 33.491, 'max_score': 555.799, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog555799.jpg'}, {'end': 722.823, 'src': 'heatmap', 'start': 657.13, 'weight': 0.763, 'content': [{'end': 659.212, 'text': 'give me the maximum merit points.', 'start': 657.13, 'duration': 2.082}, {'end': 665.884, 'text': 'yes, give me the maximum merit points that you can earn.', 'start': 659.212, 'duration': 6.672}, {'end': 677.027, 'text': 'on the array that starts from zero ends at n minus one, and before n minus one you perform three means no task were performed.', 'start': 665.884, 'duration': 11.143}, {'end': 677.687, 'text': 'Got it?', 'start': 677.467, 'duration': 0.22}, {'end': 685.229, 'text': 'So if someone writes f of two, comma one, it means give me the max merit points.', 'start': 678.127, 'duration': 7.102}, {'end': 695.294, 'text': 'Give me the max merit points that you can get if you perform the task from 0 to the second index.', 'start': 687.045, 'duration': 8.249}, {'end': 700.078, 'text': '0 to the second index, what maximum you can get in this particular section of the array.', 'start': 695.314, 'duration': 4.764}, {'end': 704.803, 'text': 'Given that, you performed task 1 right at the third index.', 'start': 700.759, 'duration': 4.044}, {'end': 706.045, 'text': 'This is what.', 'start': 705.444, 'duration': 0.601}, {'end': 708.917, 'text': 'f will be signifying.', 'start': 707.336, 'duration': 1.581}, {'end': 710.918, 'text': 'i hope that makes sense.', 'start': 708.917, 'duration': 2.001}, {'end': 714.659, 'text': "okay, now let's go on and write the recurrence.", 'start': 710.918, 'duration': 3.741}, {'end': 718.821, 'text': 'so can i say the recurrence will be quite simple, as usual.', 'start': 714.659, 'duration': 4.162}, {'end': 722.823, 'text': "if i'm starting from n minus one, where will it go?", 'start': 718.821, 'duration': 4.002}], 'summary': 'Determine maximum merit points for tasks from 0 to 2, given task 1 at index 3.', 'duration': 65.693, 'max_score': 657.13, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog657130.jpg'}], 'start': 240.165, 'title': 'Recursion, greedy algorithms, and recurrence relationships', 'summary': 'Covers the failure of greedy algorithms, emphasizing the use of recursion to solve problems and discusses solving recurrence relationships by identifying the index and introducing a parameter, with practical examples and detailed recursion logic.', 'chapters': [{'end': 309.028, 'start': 240.165, 'title': 'Recursion and greedy algorithms', 'summary': 'Discusses the failure of greedy algorithms and the approach of trying all possible ways, emphasizing the use of recursion to solve problems by expressing them in terms of index, performing operations, and finding the maximum merit points.', 'duration': 68.863, 'highlights': ['The maximum merit points that can be earned is 110, as stated by the question.', 'Emphasizing the approach of trying all possible ways when greedy algorithms fail.', 'The importance of expressing problems in terms of index, performing operations, and finding the maximum merit points when using recursion.']}, {'end': 1046.247, 'start': 309.028, 'title': 'Recurrence relationships and indexing', 'summary': 'Discusses the steps to solve recurrence relationships, focusing on identifying the index and introducing a parameter in the recurrence, with examples of applying the concept to solve a specific problem and detailing the recursion logic and base cases.', 'duration': 737.219, 'highlights': ["The first step is identifying the index and considering additional parameters in the recurrence, illustrated by using the day as the index and introducing the 'last' parameter to track the previous task performed.", "Explaining the concept of recursion and the need to consider the 'last' parameter in the recurrence to determine the task to be performed based on the previous day's task, emphasizing the importance of adhering to the given conditions.", "Detailing the base case and the logic for determining the maximum merit points by iterating through tasks and considering the 'last' parameter, emphasizing the necessity of recursion for finding the maximum merit points for different sections of the array."]}], 'duration': 806.082, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog240165.jpg', 'highlights': ['The maximum merit points that can be earned is 110, as stated by the question.', 'The importance of expressing problems in terms of index, performing operations, and finding the maximum merit points when using recursion.', "The first step is identifying the index and considering additional parameters in the recurrence, illustrated by using the day as the index and introducing the 'last' parameter to track the previous task performed.", "Explaining the concept of recursion and the need to consider the 'last' parameter in the recurrence to determine the task to be performed based on the previous day's task, emphasizing the importance of adhering to the given conditions."]}, {'end': 1575.109, 'segs': [{'end': 1069.214, 'src': 'embed', 'start': 1046.247, 'weight': 3, 'content': [{'end': 1053.29, 'text': 'just make sure you perform every task apart from the task that was performed in the other day.', 'start': 1046.247, 'duration': 7.043}, {'end': 1062.392, 'text': 'so if whenever you start off with uh, f of n minus one, whenever you start off with f of n minus one, you can pass on three right.', 'start': 1053.29, 'duration': 9.102}, {'end': 1068.214, 'text': 'so whenever you are at the last index, which is n minus one, you try out this task.', 'start': 1062.392, 'duration': 5.822}, {'end': 1069.214, 'text': 'then you try out this task.', 'start': 1068.214, 'duration': 1}], 'summary': 'Perform all tasks except the one done the previous day, passing on 3 when starting with f of n minus one.', 'duration': 22.967, 'max_score': 1046.247, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1046247.jpg'}, {'end': 1122.086, 'src': 'embed', 'start': 1091.085, 'weight': 1, 'content': [{'end': 1099.594, 'text': "just in case you're not comfortable with the recursion, let's quickly draw the recursion tree by taking n equal to four, where this is day zero.", 'start': 1091.085, 'duration': 8.509}, {'end': 1102.617, 'text': 'this is day one, this is day two and this is day three.', 'start': 1099.594, 'duration': 3.023}, {'end': 1108.561, 'text': 'okay, and the task zero is like this the task zero, task one and task two.', 'start': 1102.617, 'duration': 5.944}, {'end': 1112.483, 'text': "That is what the points you'll get if you perform them on days zeros and ones.", 'start': 1109.101, 'duration': 3.382}, {'end': 1122.086, 'text': 'So ideally what you did was you started from the bottom, like the last row, which is the third row, and you said three.', 'start': 1113.083, 'duration': 9.003}], 'summary': 'Explained recursion using a tree with n=4, tasks and days.', 'duration': 31.001, 'max_score': 1091.085, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1091085.jpg'}, {'end': 1381.53, 'src': 'heatmap', 'start': 1284.545, 'weight': 0.851, 'content': [{'end': 1288.187, 'text': 'now a very, very uh interesting question to you.', 'start': 1284.545, 'duration': 3.642}, {'end': 1289.487, 'text': 'so where were you?', 'start': 1288.187, 'duration': 1.3}, {'end': 1294.349, 'text': "you're like f of one one and you called something like you perform the task zero.", 'start': 1289.487, 'duration': 4.862}, {'end': 1298.79, 'text': 'so if you perform the task zero, what will be the points that you will add?', 'start': 1294.349, 'duration': 4.441}, {'end': 1301.671, 'text': "on f of one one, you're performing the task zero.", 'start': 1298.79, 'duration': 2.881}, {'end': 1306.213, 'text': "so on f of task zero, three, three is what you'll add if you perform task zero.", 'start': 1301.671, 'duration': 4.542}, {'end': 1311.538, 'text': "so 3 plus you're calling this f of 0, comma 0.", 'start': 1306.793, 'duration': 4.745}, {'end': 1312.499, 'text': 'remember this.', 'start': 1311.538, 'duration': 0.961}, {'end': 1316.744, 'text': "so whenever this f of 0, comma 0 goes, it's a base case.", 'start': 1312.499, 'duration': 4.245}, {'end': 1319.387, 'text': "if you remember the recurrence, it's a base case.", 'start': 1316.744, 'duration': 2.643}, {'end': 1320.648, 'text': "let's go back to the recurrence.", 'start': 1319.387, 'duration': 1.261}, {'end': 1321.569, 'text': "it's a base case.", 'start': 1320.648, 'duration': 0.921}, {'end': 1324.172, 'text': "whenever the day comes to 0, it's a base case.", 'start': 1321.569, 'duration': 2.603}, {'end': 1326.654, 'text': 'so in the base case, what did you do?', 'start': 1324.172, 'duration': 2.482}, {'end': 1327.055, 'text': "let's come back.", 'start': 1326.654, 'duration': 0.401}, {'end': 1332.551, 'text': 'you know this, that zero has been performed previously.', 'start': 1328.484, 'duration': 4.067}, {'end': 1337.859, 'text': "so either of this or either of this, and you don't have any anywhere else to go.", 'start': 1332.551, 'duration': 5.308}, {'end': 1343.83, 'text': "so if this is the only day remaining, Then you don't have to think of the future.", 'start': 1337.859, 'duration': 5.971}, {'end': 1346.571, 'text': 'So the maximum of that is 3.', 'start': 1344.23, 'duration': 2.341}, {'end': 1349.552, 'text': 'Thereby, this guy tends to return a 3.', 'start': 1346.571, 'duration': 2.981}, {'end': 1351.792, 'text': 'So this element comes out to be 3.', 'start': 1349.552, 'duration': 2.24}, {'end': 1357.354, 'text': 'Got it? Similarly, there will be this call which will be task 2.', 'start': 1351.792, 'duration': 5.562}, {'end': 1359.835, 'text': 'So if you perform task 2, which is 6.', 'start': 1357.354, 'duration': 2.481}, {'end': 1363.117, 'text': 'So, it will be like 6 plus f of 0 comma 2.', 'start': 1359.835, 'duration': 3.282}, {'end': 1368.361, 'text': 'So, if you perform this task, you can either take 2 or you can either take 1 on this guy.', 'start': 1363.117, 'duration': 5.244}, {'end': 1370.683, 'text': 'Thereby, this returns 2.', 'start': 1368.701, 'duration': 1.982}, {'end': 1373.004, 'text': 'So, you will return 2.', 'start': 1370.683, 'duration': 2.321}, {'end': 1374.145, 'text': 'So, this will be 2.', 'start': 1373.004, 'duration': 1.141}, {'end': 1376.707, 'text': 'Now, 3 plus 3 is 6.', 'start': 1374.145, 'duration': 2.562}, {'end': 1378.268, 'text': '6 plus 2 is 8.', 'start': 1376.707, 'duration': 1.561}, {'end': 1381.53, 'text': "Which one will you take? You will be like, let's take 8.", 'start': 1378.268, 'duration': 3.262}], 'summary': 'Solving a task-based problem with recursion, returns maximum value of 8.', 'duration': 96.985, 'max_score': 1284.545, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1284545.jpg'}, {'end': 1445.145, 'src': 'heatmap', 'start': 1407.433, 'weight': 0.706, 'content': [{'end': 1414.395, 'text': "you will like let's call f of zero, let's perform task zero, let's call f of zero, let's perform task one.", 'start': 1407.433, 'duration': 6.962}, {'end': 1415.335, 'text': "that's what you'll do.", 'start': 1414.395, 'duration': 0.94}, {'end': 1416.735, 'text': 'so again, same thing will happen.', 'start': 1415.335, 'duration': 1.4}, {'end': 1423.037, 'text': 'if you perform task zero, you will get three plus and f of zero zero will return three.', 'start': 1416.735, 'duration': 6.302}, {'end': 1427.778, 'text': "and if you perform f of zero one, that's task one you will get task one for four.", 'start': 1423.037, 'duration': 4.741}, {'end': 1432.72, 'text': 'so four plus, f of zero one will be what you perform zero one.', 'start': 1427.778, 'duration': 4.942}, {'end': 1435.721, 'text': "that means you're coming here and you're saying you cannot perform this.", 'start': 1432.72, 'duration': 3.001}, {'end': 1439.162, 'text': "so either of three or two, three, you'll get right.", 'start': 1435.721, 'duration': 3.441}, {'end': 1441.483, 'text': 'so either seven or six.', 'start': 1439.162, 'duration': 2.321}, {'end': 1445.145, 'text': 'thereby this gives you six perfect.', 'start': 1441.483, 'duration': 3.662}], 'summary': 'Performing task zero yields 3, while task one yields 4, resulting in a total of 6 or 7.', 'duration': 37.712, 'max_score': 1407.433, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1407433.jpg'}, {'end': 1575.109, 'src': 'embed', 'start': 1524.423, 'weight': 0, 'content': [{'end': 1526.164, 'text': 'So you saw an overlapping subproblems.', 'start': 1524.423, 'duration': 1.741}, {'end': 1531.828, 'text': "So if the value of n is larger, you'll tend to see a lot more overlapping subproblems.", 'start': 1526.544, 'duration': 5.284}, {'end': 1536.09, 'text': 'Like over here, if you go t0 and t1, it will like f of 1, 0.', 'start': 1532.188, 'duration': 3.902}, {'end': 1539.072, 'text': 'So again, overlapping subproblems over here.', 'start': 1536.09, 'duration': 2.982}, {'end': 1540.633, 'text': 'Kind of, yeah.', 'start': 1539.952, 'duration': 0.681}, {'end': 1546.094, 'text': 'So you will, the more you enlarge the tree, you will see overlapping subproblems.', 'start': 1541.892, 'duration': 4.202}, {'end': 1549.055, 'text': 'And this is how they will solve each other.', 'start': 1546.454, 'duration': 2.601}, {'end': 1551.116, 'text': 'And after that, you can easily get the answer.', 'start': 1549.536, 'duration': 1.58}, {'end': 1557.139, 'text': 'So we have again concluded that there are overlapping subproblems.', 'start': 1551.457, 'duration': 5.682}, {'end': 1562.982, 'text': 'And if there are overlapping subproblems, what do you need to do? You need to do one thing.', 'start': 1557.9, 'duration': 5.082}, {'end': 1565.483, 'text': 'What is that? Memoration.', 'start': 1563.422, 'duration': 2.061}, {'end': 1568.285, 'text': 'Yeah, And what is the easy step??', 'start': 1565.823, 'duration': 2.462}, {'end': 1573.568, 'text': 'you go back and say okay, hey, function, what are your changing parameters?', 'start': 1569.145, 'duration': 4.423}, {'end': 1575.109, 'text': 'or what are your states?', 'start': 1573.568, 'duration': 1.541}], 'summary': 'Identified overlapping subproblems, leading to efficient problem-solving. emphasized need for memoization and understanding changing parameters.', 'duration': 50.686, 'max_score': 1524.423, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1524423.jpg'}], 'start': 1046.247, 'title': 'Recursion and overlapping subproblems', 'summary': 'Delves into the concept of recursion and overlapping subproblems, stressing the importance of avoiding redundant tasks and highlighting the impact of memoization in optimization, demonstrated through specific examples and performance gains.', 'chapters': [{'end': 1134.091, 'start': 1046.247, 'title': 'Recursion and overlapping sub problems', 'summary': 'Discusses the concept of recursion and overlapping sub problems in the context of performing tasks, emphasizing the importance of avoiding tasks previously performed and showcasing a specific example with n=4, demonstrating the significance of performing tasks on different days.', 'duration': 87.844, 'highlights': ['The significance of performing tasks on different days is demonstrated with an example of n=4, showcasing the impact on the points garnered.', 'Emphasizing the importance of avoiding tasks previously performed to optimize performance.', 'Illustrating the concept of recursion and its impact on task performance and points garnered.']}, {'end': 1575.109, 'start': 1134.631, 'title': 'Recursion and overlapping subproblems', 'summary': 'Discusses the recursion pattern and overlapping subproblems, emphasizing the importance of memoization in optimizing the solution, with examples illustrating the process and its impact on performance.', 'duration': 440.478, 'highlights': ['The process involves identifying overlapping subproblems and optimizing the solution using memoization.', 'The recursion pattern is explained through examples, demonstrating the impact of changing parameters and states on the solution.', 'The example demonstrates the impact of overlapping subproblems on performance, emphasizing the need for optimization techniques.']}], 'duration': 528.862, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1046247.jpg', 'highlights': ['The process involves identifying overlapping subproblems and optimizing the solution using memoization.', 'Illustrating the concept of recursion and its impact on task performance and points garnered.', 'The example demonstrates the impact of overlapping subproblems on performance, emphasizing the need for optimization techniques.', 'Emphasizing the importance of avoiding tasks previously performed to optimize performance.', 'The significance of performing tasks on different days is demonstrated with an example of n=4, showcasing the impact on the points garnered.', 'The recursion pattern is explained through examples, demonstrating the impact of changing parameters and states on the solution.']}, {'end': 1839.719, 'segs': [{'end': 1704.795, 'src': 'heatmap', 'start': 1625.317, 'weight': 0, 'content': [{'end': 1637.083, 'text': 'so four different values which are zero one, two tasks, zero task one, task two And 3, which states that all of these tasks have been performed.', 'start': 1625.317, 'duration': 11.766}, {'end': 1638.664, 'text': 'None of these tasks have been performed.', 'start': 1637.183, 'duration': 1.481}, {'end': 1641.347, 'text': 'So, there are n 4.', 'start': 1639.125, 'duration': 2.222}, {'end': 1644.751, 'text': 'For every n state, there can be 4 different possibles.', 'start': 1641.347, 'duration': 3.404}, {'end': 1648.735, 'text': 'Thereby, you will require an n cross 4 DP size array.', 'start': 1645.291, 'duration': 3.444}, {'end': 1649.536, 'text': 'Remember this.', 'start': 1649.136, 'duration': 0.4}, {'end': 1654.361, 'text': 'Thereby, you will require an n 4 initialized with minus 1.', 'start': 1649.556, 'duration': 4.805}, {'end': 1658.622, 'text': 'n for initialized with minus one and was the first step.', 'start': 1654.361, 'duration': 4.261}, {'end': 1672.286, 'text': 'definitely over here you tend to write dp of index last equal to maxi, and over here just one line if dp of index last not equal to minus one,', 'start': 1658.622, 'duration': 13.664}, {'end': 1678.468, 'text': 'return dp of index last 2d dp done.', 'start': 1672.286, 'duration': 6.182}, {'end': 1683.009, 'text': 'if i reiterate always, the first parameter will be index.', 'start': 1678.468, 'duration': 4.541}, {'end': 1690.591, 'text': 'next, Depending on what stuff you are doing in order to preserve the condition, you might require some more.', 'start': 1683.009, 'duration': 7.582}, {'end': 1693.352, 'text': "And that's when the second parameter is introduced.", 'start': 1691.611, 'duration': 1.741}, {'end': 1694.572, 'text': 'If you require some more.', 'start': 1693.412, 'duration': 1.16}, {'end': 1696.393, 'text': 'Remember these three tricks.', 'start': 1695.212, 'duration': 1.181}, {'end': 1698.213, 'text': 'You can write any recurrence in the world.', 'start': 1696.513, 'duration': 1.7}, {'end': 1700.334, 'text': "So let's try to code this up.", 'start': 1698.733, 'duration': 1.601}, {'end': 1702.334, 'text': 'What we are given is the n and the points.', 'start': 1700.554, 'duration': 1.78}, {'end': 1704.795, 'text': "So I'll try to write the recurrence at first.", 'start': 1702.414, 'duration': 2.381}], 'summary': 'N cross 4 dp size array required for 4 possible states, with -1 initialization. recurrence and coding explained.', 'duration': 79.478, 'max_score': 1625.317, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1625317.jpg'}, {'end': 1761.245, 'src': 'embed', 'start': 1733.432, 'weight': 1, 'content': [{'end': 1736.594, 'text': 'i can go across to task and there will be three tasks.', 'start': 1733.432, 'duration': 3.162}, {'end': 1744.077, 'text': 'so task plus, plus, and we can say maxi, okay, we just need to make sure this task is not equal to the task, uh,', 'start': 1736.594, 'duration': 7.483}, {'end': 1753.381, 'text': 'done on the last rather than the last, rather so thereby this will be maximum equal to max of, uh,', 'start': 1744.077, 'duration': 9.304}, {'end': 1761.245, 'text': 'what maxi comma points on the day zero and definitely, uh, on the task.', 'start': 1753.381, 'duration': 7.864}], 'summary': 'Three tasks need to be completed, ensuring the current task is not the last one. maximum points are on the line.', 'duration': 27.813, 'max_score': 1733.432, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1733432.jpg'}, {'end': 1822.611, 'src': 'embed', 'start': 1790.83, 'weight': 3, 'content': [{'end': 1799.054, 'text': "Now, what I can do is if this task was not done on the last day, let's do this task.", 'start': 1790.83, 'duration': 8.224}, {'end': 1807.8, 'text': "But if I do this task, how many points will I generate? The points that I'll generate will be points on this day.", 'start': 1799.315, 'duration': 8.485}, {'end': 1810.182, 'text': 'this task.', 'start': 1809.201, 'duration': 0.981}, {'end': 1819.368, 'text': "if i perform plus, i'll have to go to the minus one day to solve the smaller sub problem and i'll have to tell him that, hey listen,", 'start': 1810.182, 'duration': 9.186}, {'end': 1822.611, 'text': 'this is the task that i did on the current day.', 'start': 1819.368, 'duration': 3.243}], 'summary': 'Generate points for completing task on current day.', 'duration': 31.781, 'max_score': 1790.83, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1790830.jpg'}], 'start': 1575.109, 'title': 'Dynamic programming in coding and task optimization', 'summary': 'Delves into dynamic programming in coding, emphasizing the need for an n cross 4 dp size array and initialization with minus one. it also discusses a dynamic programming algorithm for task optimization, focusing on maximizing points based on daily tasks, iterating through each task, and emphasizing three tasks.', 'chapters': [{'end': 1704.795, 'start': 1575.109, 'title': 'Dynamic programming in coding', 'summary': 'Explains the concept of dynamic programming in coding, highlighting the need for an n cross 4 dp size array and the initialization of the array with minus one.', 'duration': 129.686, 'highlights': ['The need for an n cross 4 DP size array is emphasized, as there can be 4 different possible values for every n state, requiring an array of size n cross 4.', 'The array should be initialized with minus one, as the first step in the process of dynamic programming implementation.', 'The concept of writing the recurrence for the given n and points is discussed, emphasizing the importance of preserving conditions and introducing a second parameter if necessary.']}, {'end': 1839.719, 'start': 1705.255, 'title': 'Dynamic programming task optimization', 'summary': 'Explains a dynamic programming algorithm to optimize task selection, generating maximum points based on the tasks done on each day, iterating through each task and maximizing the points, with a focus on three tasks.', 'duration': 134.464, 'highlights': ['The algorithm iterates through each task and maximizes the points for each day, focusing on three tasks, thereby optimizing task selection and generating maximum points.', 'The process involves passing on the points to the smaller subproblem, calculating the maximum points generated for each task, and returning the maximum points, resulting in an optimized task selection for maximum points.', 'The chapter discusses the concept of dynamic programming, iterating through different tasks to generate maximum points, with a focus on three tasks and the optimization of task selection.']}], 'duration': 264.61, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1575109.jpg', 'highlights': ['The need for an n cross 4 DP size array is emphasized, as there can be 4 different possible values for every n state, requiring an array of size n cross 4.', 'The algorithm iterates through each task and maximizes the points for each day, focusing on three tasks, thereby optimizing task selection and generating maximum points.', 'The array should be initialized with minus one, as the first step in the process of dynamic programming implementation.', 'The process involves passing on the points to the smaller subproblem, calculating the maximum points generated for each task, and returning the maximum points, resulting in an optimized task selection for maximum points.', 'The concept of writing the recurrence for the given n and points is discussed, emphasizing the importance of preserving conditions and introducing a second parameter if necessary.', 'The chapter discusses the concept of dynamic programming, iterating through different tasks to generate maximum points, with a focus on three tasks and the optimization of task selection.']}, {'end': 2494.102, 'segs': [{'end': 2010.739, 'src': 'heatmap', 'start': 1839.759, 'weight': 0, 'content': [{'end': 1845.821, 'text': 'So, now I can return the function n-1, initially start off with 3, and we can definitely pass on the points.', 'start': 1839.759, 'duration': 6.062}, {'end': 1847.282, 'text': 'Then it should be fine.', 'start': 1846.602, 'duration': 0.68}, {'end': 1848.323, 'text': "So, I'll just give it a run.", 'start': 1847.302, 'duration': 1.021}, {'end': 1852.564, 'text': 'So, as you can see, there is time limit exceeded.', 'start': 1850.664, 'duration': 1.9}, {'end': 1856.319, 'text': "So let's memorize it so that's.", 'start': 1852.584, 'duration': 3.735}, {'end': 1863.122, 'text': "that's the way you can create dp variables, dp, and then you can give the first size, which is n.", 'start': 1856.319, 'duration': 6.803}, {'end': 1867.503, 'text': 'then you can declare the second uh one which is vector of int.', 'start': 1863.122, 'duration': 4.381}, {'end': 1869.364, 'text': 'uh four size and a minus one.', 'start': 1867.503, 'duration': 1.861}, {'end': 1874.606, 'text': "that's how you declare a 2d's array, 2d dp array of n cross at foreign vector.", 'start': 1869.364, 'duration': 5.242}, {'end': 1875.066, 'text': 'why vector?', 'start': 1874.606, 'duration': 0.46}, {'end': 1878.388, 'text': 'because i generally write prefer vectors.', 'start': 1875.066, 'duration': 3.322}, {'end': 1880.348, 'text': "it's very easier to pass in reference.", 'start': 1878.388, 'duration': 1.96}, {'end': 1885.26, 'text': "that's the only reason Java people can probably do arrays, not a big stuff.", 'start': 1880.348, 'duration': 4.912}, {'end': 1895.018, 'text': "By the way, for Java people, you'll find the code links in the description, okay? So, dp is done and yeah, you're calling f over here.", 'start': 1885.62, 'duration': 9.398}, {'end': 1896.439, 'text': 'So, you can just pass on the dp over here.', 'start': 1895.038, 'duration': 1.401}, {'end': 1902.103, 'text': "Right over here, you can say dp of probably day and then there's something that's last.", 'start': 1896.98, 'duration': 5.123}, {'end': 1907.227, 'text': 'So, you can just give it like this and right before returning, just make sure you check it across.', 'start': 1902.143, 'duration': 5.084}, {'end': 1910.97, 'text': 'If dp of day last, this sub problem has been previously solved.', 'start': 1907.647, 'duration': 3.323}, {'end': 1917.094, 'text': 'If this sub problem has been previously solved, what you can do is dp of day and you can say last.', 'start': 1911.43, 'duration': 5.664}, {'end': 1920.036, 'text': "Can you please return that? And now, let's code this up.", 'start': 1917.514, 'duration': 2.522}, {'end': 1924.879, 'text': 'it gives me a correct answer.', 'start': 1923.297, 'duration': 1.582}, {'end': 1927.521, 'text': "now let's quickly submit this.", 'start': 1924.879, 'duration': 2.642}, {'end': 1932.646, 'text': 'as you see, i was solving this before this class and yeah, it it runs.', 'start': 1927.521, 'duration': 5.125}, {'end': 1939.373, 'text': 'so we used recursion plus optimization in order to solve this particular problem.', 'start': 1932.646, 'duration': 6.727}, {'end': 1945.9, 'text': "that's time to check out the next possible stuff, which is tabulation, just in order to reduce the stack space.", 'start': 1939.373, 'duration': 6.527}, {'end': 1949.415, 'text': "So what's the next step?", 'start': 1947.432, 'duration': 1.983}, {'end': 1960.492, 'text': 'The next step is tabulation, because the recursion, as we saw we were using something like the time complexity of memoization, will be n crossed,', 'start': 1949.736, 'duration': 10.756}, {'end': 1962.85, 'text': 'Because, see, there are n cross 4 steps.', 'start': 1960.828, 'duration': 2.022}, {'end': 1966.954, 'text': 'Understand how many different states we can have.', 'start': 1963.19, 'duration': 3.764}, {'end': 1969.857, 'text': "that's n cross 4, right?", 'start': 1966.954, 'duration': 2.903}, {'end': 1977.705, 'text': "Like, not in all cases we'll have 4 states, but yeah, let's assume for the worst case it's n cross 4 states that we can have.", 'start': 1970.217, 'duration': 7.488}, {'end': 1980.248, 'text': 'If you carefully observe, for every state.', 'start': 1978.346, 'duration': 1.902}, {'end': 1986.156, 'text': 'we were actually, uh, running a for loop of size two, like for every state, or size three.', 'start': 1980.808, 'duration': 5.348}, {'end': 1992.504, 'text': "rather. so for every state, you're running a for loop of size three, so i can say it's n cross it.", 'start': 1986.156, 'duration': 6.348}, {'end': 1995.589, 'text': '12 is the time complexity and space complexity of.', 'start': 1992.504, 'duration': 3.085}, {'end': 2005.277, 'text': 'we go off recursion stack space will be n, because at max you will go for n days, but the space complexity will be n cross at four.', 'start': 1995.589, 'duration': 9.688}, {'end': 2010.739, 'text': 'so this will be the recursion plus memoization time complexity.', 'start': 2005.277, 'duration': 5.462}], 'summary': 'Using recursion and optimization, solved problem with time complexity of n*12 and space complexity of n*4.', 'duration': 45.501, 'max_score': 1839.759, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1839759.jpg'}, {'end': 2012.2, 'src': 'embed', 'start': 1986.156, 'weight': 3, 'content': [{'end': 1992.504, 'text': "rather. so for every state, you're running a for loop of size three, so i can say it's n cross it.", 'start': 1986.156, 'duration': 6.348}, {'end': 1995.589, 'text': '12 is the time complexity and space complexity of.', 'start': 1992.504, 'duration': 3.085}, {'end': 2005.277, 'text': 'we go off recursion stack space will be n, because at max you will go for n days, but the space complexity will be n cross at four.', 'start': 1995.589, 'duration': 9.688}, {'end': 2010.739, 'text': 'so this will be the recursion plus memoization time complexity.', 'start': 2005.277, 'duration': 5.462}, {'end': 2012.2, 'text': 'and this is an extra.', 'start': 2010.739, 'duration': 1.461}], 'summary': 'Time complexity is o(12), space complexity is o(n^4).', 'duration': 26.044, 'max_score': 1986.156, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1986156.jpg'}, {'end': 2311.123, 'src': 'embed', 'start': 2277.907, 'weight': 4, 'content': [{'end': 2282.629, 'text': 'right. so we we can definitely, uh, follow this.', 'start': 2277.907, 'duration': 4.722}, {'end': 2285.35, 'text': 'so thereby we know for every day.', 'start': 2282.629, 'duration': 2.721}, {'end': 2287.651, 'text': "so let's first write the code for day.", 'start': 2285.35, 'duration': 2.301}, {'end': 2292.172, 'text': "so, if i know that i'm gonna start, because what is tabulation?", 'start': 2287.651, 'duration': 4.521}, {'end': 2294.953, 'text': 'previous classes, guys, what is tabulation?', 'start': 2292.172, 'duration': 2.781}, {'end': 2301.916, 'text': 'tabulation is nothing but bottom up.', 'start': 2294.953, 'duration': 6.963}, {'end': 2309.901, 'text': "so from zero to the up, like if i show you the recursion tree, You'll start from here.", 'start': 2301.916, 'duration': 7.985}, {'end': 2311.123, 'text': "Then you'll compute this.", 'start': 2310.082, 'duration': 1.041}], 'summary': 'Discussing coding concepts related to tabulation and recursion tree.', 'duration': 33.216, 'max_score': 2277.907, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog2277907.jpg'}, {'end': 2444.431, 'src': 'embed', 'start': 2415.353, 'weight': 5, 'content': [{'end': 2423.798, 'text': "so in order to write the tabulation, what you will do is you'll declare a dp array of n cross 4 and super quickly write something like 0 on 0,", 'start': 2415.353, 'duration': 8.445}, {'end': 2432.083, 'text': 'with a max of definitely points of 0 of 1 comma, points of 0, comma 2.', 'start': 2423.798, 'duration': 8.285}, {'end': 2435.168, 'text': "that's very obvious And similar.", 'start': 2432.083, 'duration': 3.085}, {'end': 2441.11, 'text': 'I can just copy paste this thing for the other tasks, which is task one.', 'start': 2435.168, 'duration': 5.942}, {'end': 2444.431, 'text': "So if you're doing task one, this will be zero and two.", 'start': 2441.55, 'duration': 2.881}], 'summary': 'To write the tabulation, declare a dp array of n x 4 and quickly note the points as 0, 0, 0, 1, 0, 2; copy-paste for other tasks.', 'duration': 29.078, 'max_score': 2415.353, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog2415353.jpg'}], 'start': 1839.759, 'title': 'Dynamic programming in c++ and tabulation for optimization', 'summary': 'Discusses the implementation of dynamic programming in c++ focusing on creating a 2d dp array and using memoization, achieving improved efficiency. it also covers tabulation as an optimization technique with a time complexity of o(n*4) and space complexity of o(n*4) for conversion to a dynamic programming solution.', 'chapters': [{'end': 1932.646, 'start': 1839.759, 'title': 'Dynamic programming in c++', 'summary': 'Discusses the implementation of dynamic programming in c++ with a focus on creating a 2d dp array and using memoization to solve subproblems, resulting in improved efficiency and successful problem solving in the provided example.', 'duration': 92.887, 'highlights': ['The chapter explains the creation of a 2D DP array in C++ using vectors, highlighting the advantage of using vectors for passing by reference and declaring a 2D array of size n.', 'The speaker emphasizes the importance of memoization in dynamic programming, illustrating the process of checking if a subproblem has been previously solved using the DP array and returning the result if available.', 'The transcript provides an example of implementing dynamic programming in C++ to solve a problem, demonstrating the successful execution and submission of the code.']}, {'end': 2494.102, 'start': 1932.646, 'title': 'Tabulation for optimization', 'summary': 'Discusses the optimization technique of tabulation as an alternative to recursion, achieving a time complexity of o(n*4) and space complexity of o(n*4) with detailed steps and base cases for conversion to a dynamic programming solution.', 'duration': 561.456, 'highlights': ['The time complexity of the recursion with memoization is O(n*12) and the space complexity is O(n*4), highlighting the need for an alternative optimization technique like tabulation.', 'The first rule of tabulation is to declare a similar size dp array and establish base cases for the 2D DPs, such as dp[0][0] = max(array[0], task 1, task 2).', 'The conversion to a dynamic programming solution involves bottom-up computation for every day and last, involving a for loop for day and last to perform the tasks, resulting in a tabulation technique to optimize the solution.']}], 'duration': 654.343, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog1839759.jpg', 'highlights': ['The chapter explains the creation of a 2D DP array in C++ using vectors, highlighting the advantage of using vectors for passing by reference and declaring a 2D array of size n.', 'The speaker emphasizes the importance of memoization in dynamic programming, illustrating the process of checking if a subproblem has been previously solved using the DP array and returning the result if available.', 'The transcript provides an example of implementing dynamic programming in C++ to solve a problem, demonstrating the successful execution and submission of the code.', 'The time complexity of the recursion with memoization is O(n*12) and the space complexity is O(n*4), highlighting the need for an alternative optimization technique like tabulation.', 'The conversion to a dynamic programming solution involves bottom-up computation for every day and last, involving a for loop for day and last to perform the tasks, resulting in a tabulation technique to optimize the solution.', 'The first rule of tabulation is to declare a similar size dp array and establish base cases for the 2D DPs, such as dp[0][0] = max(array[0], task 1, task 2).']}, {'end': 3128.822, 'segs': [{'end': 2649.815, 'src': 'heatmap', 'start': 2599.444, 'weight': 0, 'content': [{'end': 2606.63, 'text': 'So you store it in the DP and yeah, you just keep it DP of day last.', 'start': 2599.444, 'duration': 7.186}, {'end': 2611.514, 'text': 'Instead of using a maxi variable, what I did was I just used this particular stuff.', 'start': 2607.45, 'duration': 4.064}, {'end': 2612.634, 'text': "So I'll just omit this.", 'start': 2611.634, 'duration': 1}, {'end': 2613.996, 'text': 'And where is your answer?', 'start': 2613.175, 'duration': 0.821}, {'end': 2621.114, 'text': 'The initial call that you made the recursion, the initial call that you made to recursion was F of n minus 1.', 'start': 2615.011, 'duration': 6.103}, {'end': 2623.335, 'text': 'if you have n minus 1 and 3.', 'start': 2621.114, 'duration': 2.221}, {'end': 2624.215, 'text': 'So this made it.', 'start': 2623.335, 'duration': 0.88}, {'end': 2625.155, 'text': 'just make it.', 'start': 2624.215, 'duration': 0.94}, {'end': 2632.739, 'text': 'and now what I can do is you can definitely run this and you see this running fine, Yeah, and it is submitted.', 'start': 2625.155, 'duration': 7.584}, {'end': 2633.939, 'text': 'Was tabulation tough?', 'start': 2632.739, 'duration': 1.2}, {'end': 2636.781, 'text': 'Who was it if you would have written recursion??', 'start': 2634.5, 'duration': 2.281}, {'end': 2640.082, 'text': 'It was not.', 'start': 2637.401, 'duration': 2.681}, {'end': 2643.083, 'text': 'I Told you not in the starting of the DP playlist.', 'start': 2640.082, 'duration': 3.001}, {'end': 2644.504, 'text': 'once I teach you DP.', 'start': 2643.083, 'duration': 1.421}, {'end': 2645.934, 'text': "I You'll never forget it.", 'start': 2644.544, 'duration': 1.39}, {'end': 2649.815, 'text': "So that's how I wrote the wonderful recursion.", 'start': 2646.314, 'duration': 3.501}], 'summary': 'Utilized dynamic programming to optimize recursion for efficient code. emphasized ease of understanding and successful implementation.', 'duration': 24.66, 'max_score': 2599.444, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog2599444.jpg'}, {'end': 3051.639, 'src': 'heatmap', 'start': 3007.945, 'weight': 0.849, 'content': [{'end': 3019.288, 'text': "Now, let's make the DPS temp so that again on the next day, Again, on the next day, when this guy has been computed, this can serve as for this guy.", 'start': 3007.945, 'duration': 11.343}, {'end': 3020.508, 'text': 'And we can again compute this.', 'start': 3019.508, 'duration': 1}, {'end': 3021.588, 'text': 'So, we keep on doing.', 'start': 3020.828, 'duration': 0.76}, {'end': 3027.73, 'text': 'And at the end of the day, instead of this, I can say the previous has my answer.', 'start': 3022.128, 'duration': 5.602}, {'end': 3028.29, 'text': 'Oh, sorry.', 'start': 3027.97, 'duration': 0.32}, {'end': 3029.23, 'text': 'This will be previous.', 'start': 3028.55, 'duration': 0.68}, {'end': 3030.831, 'text': 'The previous has my answer.', 'start': 3029.751, 'duration': 1.08}, {'end': 3036.833, 'text': 'Right? And once the previous has your answer, you can definitely run it.', 'start': 3032.831, 'duration': 4.002}, {'end': 3037.813, 'text': "Let's see if it runs.", 'start': 3036.973, 'duration': 0.84}, {'end': 3042.213, 'text': "yeah, it runs and now let's try to submit it.", 'start': 3038.871, 'duration': 3.342}, {'end': 3046.696, 'text': 'it runs and look at the time 4, 26 a.m in the morning.', 'start': 3042.213, 'duration': 4.483}, {'end': 3051.639, 'text': 'and uh, i hope i was able to make you understand.', 'start': 3046.696, 'duration': 4.943}], 'summary': 'Iterative computation completed at 4:26 a.m., successful submission made.', 'duration': 43.694, 'max_score': 3007.945, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog3007945.jpg'}, {'end': 3086.803, 'src': 'embed', 'start': 3051.639, 'weight': 1, 'content': [{'end': 3054.761, 'text': 'and the time complexity now boils down to n cross 4, cross 3.', 'start': 3051.639, 'duration': 3.122}, {'end': 3056.082, 'text': 'but what about the space?', 'start': 3054.761, 'duration': 1.321}, {'end': 3061.786, 'text': "i'm just using a 4 size, which is as good as constant, which is as good as constant.", 'start': 3056.082, 'duration': 5.704}, {'end': 3067.494, 'text': 'i converted a 2d matrix is to as good as constant, like one d.', 'start': 3061.786, 'duration': 5.708}, {'end': 3070.776, 'text': 'again, cross four into four, which is very, very good.', 'start': 3067.494, 'duration': 3.282}, {'end': 3073.137, 'text': "so that's about the space optimization.", 'start': 3070.776, 'duration': 2.361}, {'end': 3077.46, 'text': "i think i'm gone with voice because it's it's a very, very long video.", 'start': 3073.137, 'duration': 4.323}, {'end': 3086.803, 'text': 'so, guys, i hope i was able to explain you the entire problem, all the three approaches, just in case i was, please, please, please give me a like,', 'start': 3077.46, 'duration': 9.343}], 'summary': 'Optimized time complexity to o(n*4*3) and space complexity to o(4), converting 2d to 1d, achieving efficiency.', 'duration': 35.164, 'max_score': 3051.639, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog3051639.jpg'}], 'start': 2494.102, 'title': 'Dynamic programming and space optimization', 'summary': 'Covers dynamic programming, focusing on bottom-up approach, tabulation, time and space complexity, with a time complexity of n cross 4 cross 3 and a space complexity of n cross 4. it also delves into space optimization, reducing space complexity to a constant 4 size array while maintaining time complexity of n cross 4 cross 3.', 'chapters': [{'end': 2675.751, 'start': 2494.102, 'title': 'Dynamic programming explained', 'summary': 'Discusses the process of dynamic programming, emphasizing the bottom-up approach, tabulation, and the time and space complexity, with a time complexity of n cross 4 cross 3 and a space complexity of n cross 4.', 'duration': 181.649, 'highlights': ['The chapter emphasizes the bottom-up approach of dynamic programming, focusing on the process of tabulation and its benefits over recursion.', 'The process of dynamic programming is explained with a time complexity of n cross 4 cross 3 and a space complexity of n cross 4.']}, {'end': 3128.822, 'start': 2675.751, 'title': 'Space optimization in dynamic programming', 'summary': 'Explains space optimization in dynamic programming by showing how to reduce the space complexity from n cross 4 to a constant 4 size array while maintaining a time complexity of n cross 4 cross 3.', 'duration': 453.071, 'highlights': ['The chapter explains how to reduce space complexity in dynamic programming from n cross 4 to a constant 4 size array.', 'The time complexity is reduced to n cross 4 cross 3 while maintaining a space complexity of a constant 4 size array.', 'The speaker emphasizes the significance of audience engagement through likes, comments, and subscriptions.']}], 'duration': 634.72, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AE39gJYuRog/pics/AE39gJYuRog2494102.jpg', 'highlights': ['The chapter emphasizes the bottom-up approach of dynamic programming, focusing on tabulation.', 'The process of dynamic programming has a time complexity of n cross 4 cross 3 and a space complexity of n cross 4.', 'The chapter explains how to reduce space complexity to a constant 4 size array while maintaining time complexity of n cross 4 cross 3.']}], 'highlights': ['The time complexity of the recursion with memoization is O(n*12) and the space complexity is O(n*4), highlighting the need for an alternative optimization technique like tabulation.', 'The process of dynamic programming has a time complexity of n cross 4 cross 3 and a space complexity of n cross 4.', 'The chapter explains how to reduce space complexity to a constant 4 size array while maintaining time complexity of n cross 4 cross 3.', 'The need for an n cross 4 DP size array is emphasized, as there can be 4 different possible values for every n state, requiring an array of size n cross 4.', 'The algorithm iterates through each task and maximizes the points for each day, focusing on three tasks, thereby optimizing task selection and generating maximum points.']}