title
DP 3. Frog Jump | Dynamic Programming | Learn to write 1D DP

description
Lecture Notes/C++/Java Codes: https://takeuforward.org/data-structure/dynamic-programming-frog-jump-dp-3/ Problem Link: https://bit.ly/3JPcoOx Make sure to join our telegram group for discussions: https://linktr.ee/takeUforward Pre-req for this Series: https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9 Full Playlist: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY In this video, we have discussed how to solve the frog jump problem. I have taught you how you should write a 1D recurrence. Also, I have given you a follow-up problem to which you can answer in the comments. We will solve that follow-up problem in the L4. 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 3. Frog Jump | Dynamic Programming | Learn to write 1D DP', 'heatmap': [{'end': 608.469, 'start': 440.238, 'weight': 0.745}, {'end': 752.411, 'start': 693.45, 'weight': 0.875}, {'end': 910.318, 'start': 861.575, 'weight': 0.744}, {'end': 1283.005, 'start': 1234.969, 'weight': 0.862}, {'end': 1569.344, 'start': 1513.83, 'weight': 0.726}, {'end': 1732.895, 'start': 1602.685, 'weight': 0.727}, {'end': 1787.998, 'start': 1741.382, 'weight': 0.777}, {'end': 1865.539, 'start': 1839.416, 'weight': 0.793}, {'end': 2121.954, 'start': 2087.016, 'weight': 0.783}], 'summary': 'Delves into optimizing energy usage for a frog jumping on varying height staircases, quantifying the minimum energy required for specific jumps and illustrating paths with minimal energy requirements, while emphasizing the ineffectiveness of a greedy solution and the need to explore all possible ways to find the best solution. it covers recursion, memoization, tabulation, and space optimization in dynamic programming, providing step-by-step explanations and emphasizing problem-solving steps.', 'chapters': [{'end': 191.389, 'segs': [{'end': 100.149, 'src': 'embed', 'start': 46.818, 'weight': 0, 'content': [{'end': 54.762, 'text': 'so uh, the energy lost in the jump is given by height i minus one and height j minus one.', 'start': 46.818, 'duration': 7.944}, {'end': 55.582, 'text': 'so basically,', 'start': 54.762, 'duration': 0.82}, {'end': 64.388, 'text': 'the frog can jump from the ith stair to the jth stair and the energy will be a height of i minus one minus height of j minus one In the frog.', 'start': 55.582, 'duration': 8.806}, {'end': 68.73, 'text': 'if the frog is in the i-th staircase, he can jump from either.', 'start': 64.388, 'duration': 4.342}, {'end': 73.053, 'text': 'he can jump either to i plus 1-th stair or to i plus 2-th stair.', 'start': 68.73, 'duration': 4.323}, {'end': 78.076, 'text': 'Basically, he can take a jump to the plus 1 index or to the plus 2 index.', 'start': 73.073, 'duration': 5.003}, {'end': 85.661, 'text': 'Your task is to find the minimum total energy used by the frog to reach the first stair to the n-th stair.', 'start': 78.837, 'duration': 6.824}, {'end': 88.302, 'text': 'Okay, so that is what the question states.', 'start': 86.041, 'duration': 2.261}, {'end': 93.344, 'text': "So, for an example, I'll just take the first example, 10, 20..", 'start': 88.743, 'duration': 4.601}, {'end': 100.149, 'text': "30 and 10 okay and i'll try to explain you this let's take the first example which is 10 20 30 and 10.", 'start': 93.345, 'duration': 6.804}], 'summary': 'Calculate minimum energy for frog to jump from 1st to n-th stair.', 'duration': 53.331, 'max_score': 46.818, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ46818.jpg'}, {'end': 147.143, 'src': 'embed', 'start': 118.456, 'weight': 2, 'content': [{'end': 128.342, 'text': 'So, if the frog starts from here and he can only jump one or two places, what is the minimum energy that he will require?', 'start': 118.456, 'duration': 9.886}, {'end': 139.778, 'text': 'So, for example, if the frog is here and the frog says that okay, I will jump from here to here, then the energy that he will require is 10..', 'start': 129.144, 'duration': 10.634}, {'end': 142.34, 'text': "Okay And then he decides that he'll jump from here to here.", 'start': 139.778, 'duration': 2.562}, {'end': 145.682, 'text': 'And the energy again required will be 10.', 'start': 142.84, 'duration': 2.842}, {'end': 147.143, 'text': "It's a difference of them.", 'start': 145.682, 'duration': 1.461}], 'summary': 'Frog needs minimum 10 energy to jump between spots.', 'duration': 28.687, 'max_score': 118.456, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ118456.jpg'}], 'start': 0.029, 'title': "Frog's energy optimization", 'summary': 'Delves into optimizing energy usage for a frog jumping on varying height staircases, emphasizing the importance of previous knowledge and providing detailed explanations. it also quantifies the minimum energy required for specific jumps and illustrates paths with minimal energy requirements.', 'chapters': [{'end': 118.096, 'start': 0.029, 'title': 'Frog jump dynamic programming', 'summary': 'Discusses the problem of a frog jumping on a staircase with varying heights, aiming to minimize the total energy used to reach the last stair. it emphasizes the importance of watching the previous lectures and provides a detailed explanation of the problem and its constraints.', 'duration': 118.067, 'highlights': ['The frog can jump from the ith stair to the jth stair, with the energy lost in the jump being height i minus one minus height j minus one, and it can jump from the ith stair to either the i plus 1th stair or the i plus 2th stair, requiring the minimum total energy to reach the last stair.', 'The problem involves a frog on a staircase with a given height for each stair, aiming to minimize the total energy used to reach the last stair, exemplified with a specific set of heights for better understanding.']}, {'end': 191.389, 'start': 118.456, 'title': "Frog's minimum energy", 'summary': 'Discusses the minimum energy required by a frog to jump one or two places, with the energy difference between each jump and finding the path with the minimum energy requirement, illustrating with examples and quantifying the energy required for each path.', 'duration': 72.933, 'highlights': ["The frog's minimum energy requirement is illustrated through different paths, with the energy required for each path quantified, such as 40, 20, and 40.", "The chapter emphasizes the limitation on the frog's jump to one or two places, leading to a quantified energy requirement of 40 for a specific path.", 'The energy difference between each jump is quantified, with examples showing an energy requirement of 10 for a specific jump.']}], 'duration': 191.36, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ29.jpg', 'highlights': ['The frog can jump from the ith stair to the jth stair, with the energy lost in the jump being height i minus one minus height j minus one, and it can jump from the ith stair to either the i plus 1th stair or the i plus 2th stair, requiring the minimum total energy to reach the last stair.', 'The problem involves a frog on a staircase with a given height for each stair, aiming to minimize the total energy used to reach the last stair, exemplified with a specific set of heights for better understanding.', "The frog's minimum energy requirement is illustrated through different paths, with the energy required for each path quantified, such as 40, 20, and 40.", "The chapter emphasizes the limitation on the frog's jump to one or two places, leading to a quantified energy requirement of 40 for a specific path.", 'The energy difference between each jump is quantified, with examples showing an energy requirement of 10 for a specific jump.']}, {'end': 391.319, 'segs': [{'end': 216.373, 'src': 'embed', 'start': 191.389, 'weight': 0, 'content': [{'end': 197.09, 'text': "So if you see, I've tried out one possible way, two possible way, three possible way.", 'start': 191.389, 'duration': 5.701}, {'end': 200.911, 'text': 'And the minimum that I encounter is 20.', 'start': 197.61, 'duration': 3.301}, {'end': 205.732, 'text': 'And you have to tell me what is the minimal energy that you can take.', 'start': 200.911, 'duration': 4.821}, {'end': 206.812, 'text': 'And that is what the question is.', 'start': 205.852, 'duration': 0.96}, {'end': 209.567, 'text': 'now, uh, can i say this?', 'start': 207.705, 'duration': 1.862}, {'end': 216.373, 'text': 'can i say this that, uh, this question again gives me an idea that you are trying always.', 'start': 209.567, 'duration': 6.806}], 'summary': 'Minimum energy encountered is 20, seeking minimal energy.', 'duration': 24.984, 'max_score': 191.389, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ191389.jpg'}, {'end': 260.671, 'src': 'embed', 'start': 235.996, 'weight': 3, 'content': [{'end': 241.639, 'text': 'Why will a greedy solution not work over here? That might be a question that comes to your head.', 'start': 235.996, 'duration': 5.643}, {'end': 246.782, 'text': "So that's the first thing that I will be talking about, why a greedy solution doesn't works.", 'start': 242.12, 'duration': 4.662}, {'end': 248.764, 'text': "Let's understand that.", 'start': 248.003, 'duration': 0.761}, {'end': 253.887, 'text': "Then after that, we'll think why we need to try all possible ways and need to take the best way out.", 'start': 248.964, 'duration': 4.923}, {'end': 257.829, 'text': 'So when I say greedy, that means you are standing from 10.', 'start': 254.367, 'duration': 3.462}, {'end': 260.671, 'text': 'So you know from 10, you can go to 20 or go to 30.', 'start': 257.829, 'duration': 2.842}], 'summary': "Discussing why a greedy solution doesn't work and the need to consider all possible ways.", 'duration': 24.675, 'max_score': 235.996, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ235996.jpg'}, {'end': 308.053, 'src': 'embed', 'start': 277.606, 'weight': 4, 'content': [{'end': 278.807, 'text': 'whichever takes minimal energy.', 'start': 277.606, 'duration': 1.201}, {'end': 282.911, 'text': "you try to jump that, but why a greedy solution doesn't works?", 'start': 278.807, 'duration': 4.104}, {'end': 283.471, 'text': "let's check that out.", 'start': 282.911, 'duration': 0.56}, {'end': 287.235, 'text': "Now. when I say a greedy solution doesn't work out, let's check this test case.", 'start': 284.312, 'duration': 2.923}, {'end': 294.721, 'text': 'So if the frog was here, if the frog was here greedily from here, he will try to move here, because in moving here it will take him 30,', 'start': 287.795, 'duration': 6.926}, {'end': 296.703, 'text': 'it will take him 20..', 'start': 294.721, 'duration': 1.982}, {'end': 298.404, 'text': 'The greedy option will be to move to 10.', 'start': 296.703, 'duration': 1.701}, {'end': 302.668, 'text': "So, let's greedily move to 10, which will cost him a 20, okay.", 'start': 298.404, 'duration': 4.264}, {'end': 308.053, 'text': 'Now, again, from here, he can move here, which is 50 or he can move here, which is 0.', 'start': 303.229, 'duration': 4.824}], 'summary': "Testing a greedy solution for frog's movement with varying energy costs.", 'duration': 30.447, 'max_score': 277.606, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ277606.jpg'}, {'end': 391.319, 'src': 'embed', 'start': 341.144, 'weight': 1, 'content': [{'end': 346.126, 'text': "right, and if he decides after that he'll go to 60 again, that will cost him zero.", 'start': 341.144, 'duration': 4.982}, {'end': 349.127, 'text': "and after that he decides he'll go 50, that will cost him 10..", 'start': 346.126, 'duration': 3.001}, {'end': 351.688, 'text': 'so a total of 40 will be the costing.', 'start': 349.127, 'duration': 2.561}, {'end': 353.669, 'text': 'a total of 40 will be the costing.', 'start': 351.688, 'duration': 1.981}, {'end': 363.372, 'text': 'so we did realize the greedy way did not give you the correct path because you started greedily but you lost out, probably somewhere right.', 'start': 353.669, 'duration': 9.703}, {'end': 368.642, 'text': "so that's why, that's why it's better if you try all possible ways,", 'start': 363.372, 'duration': 5.27}, {'end': 376.248, 'text': 'because sometimes it will happen that initially you took the better way but you lost out on something significant like this.', 'start': 368.642, 'duration': 7.606}, {'end': 378.409, 'text': '60 to 60 would have been zero.', 'start': 376.248, 'duration': 2.161}, {'end': 380.471, 'text': 'you lost out in future.', 'start': 378.409, 'duration': 2.062}, {'end': 386.375, 'text': "so in such cases greedy doesn't works and you have to try recursion.", 'start': 380.471, 'duration': 5.904}, {'end': 391.319, 'text': 'now, when i say recursion boils down to the second lecture.', 'start': 386.375, 'duration': 4.944}], 'summary': 'Choosing the greedy way cost 40, recursion is necessary for optimal paths.', 'duration': 50.175, 'max_score': 341.144, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ341144.jpg'}], 'start': 191.389, 'title': 'Energy minimization problem', 'summary': 'Discusses the energy minimization problem with a minimum encountered energy of 20. it emphasizes the ineffectiveness of a greedy solution and the need to explore all possible ways to find the best solution. it also compares the inefficiency of greedy algorithms in finding the optimal path with the need for recursion to avoid losing out on significant outcomes.', 'chapters': [{'end': 257.829, 'start': 191.389, 'title': 'Energy minimization problem', 'summary': 'Discusses the energy minimization problem, where the minimum encountered energy is 20, and explores why a greedy solution will not work and emphasizes the need to try all possible ways to find the best solution.', 'duration': 66.44, 'highlights': ['The minimum encountered energy is 20, and the task is to determine the minimal energy that can be taken.', 'The discussion explains why a greedy solution will not work for the energy minimization problem.', 'Emphasizes the need to try all possible ways and take the best way out for solving the energy minimization problem.']}, {'end': 391.319, 'start': 257.829, 'title': 'Greedy vs recursion', 'summary': "Explains the concept of greedy algorithms using a frog's movement example, comparing its inefficiency in finding the optimal path with the need for recursion to explore all possible ways and avoid losing out on significant outcomes.", 'duration': 133.49, 'highlights': ['The greedy solution fails to find the optimal path in the example, resulting in a total cost of 60 compared to the recursive approach which finds the optimal path with a total cost of 40.', 'The importance of exploring all possible ways and avoiding the loss of significant outcomes is highlighted as a reason for preferring a recursive approach over a greedy one.', "The concept of greedy algorithms is explained using a frog's movement example, emphasizing the attempt to minimize energy and take the minimal possible jumps."]}], 'duration': 199.93, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ191389.jpg', 'highlights': ['The minimum encountered energy is 20, and the task is to determine the minimal energy that can be taken.', 'The importance of exploring all possible ways and avoiding the loss of significant outcomes is highlighted as a reason for preferring a recursive approach over a greedy one.', 'The greedy solution fails to find the optimal path in the example, resulting in a total cost of 60 compared to the recursive approach which finds the optimal path with a total cost of 40.', 'The discussion explains why a greedy solution will not work for the energy minimization problem.', "The concept of greedy algorithms is explained using a frog's movement example, emphasizing the attempt to minimize energy and take the minimal possible jumps.", 'Emphasizes the need to try all possible ways and take the best way out for solving the energy minimization problem.']}, {'end': 716.47, 'segs': [{'end': 608.469, 'src': 'heatmap', 'start': 417.71, 'weight': 0, 'content': [{'end': 421.865, 'text': 'express the problem in terms of index.', 'start': 417.71, 'duration': 4.155}, {'end': 424.647, 'text': 'do all stuffs on that index.', 'start': 421.865, 'duration': 2.782}, {'end': 426.809, 'text': 'remember this to write recursion.', 'start': 424.647, 'duration': 2.162}, {'end': 431.312, 'text': 'do all stuffs on that index.', 'start': 426.809, 'duration': 4.503}, {'end': 436.816, 'text': "step three over here they're asking you to find the minimum energy, minimum energy that you took.", 'start': 431.312, 'duration': 5.504}, {'end': 440.238, 'text': 'so take the minimal of all stuffs.', 'start': 436.816, 'duration': 3.422}, {'end': 442.76, 'text': 'take the minimal of all stuffs.', 'start': 440.238, 'duration': 2.522}, {'end': 445.382, 'text': 'this is how you write recursion.', 'start': 442.76, 'duration': 2.622}, {'end': 450.163, 'text': 'okay, so can i say I am wanting to reach the index n minus 1..', 'start': 445.382, 'duration': 4.781}, {'end': 453.085, 'text': 'I am assuming zero-based indexing.', 'start': 450.163, 'duration': 2.922}, {'end': 456.007, 'text': 'So, I am wanting to reach the index n minus 1.', 'start': 453.105, 'duration': 2.902}, {'end': 456.947, 'text': 'So what do I want?', 'start': 456.007, 'duration': 0.94}, {'end': 459.229, 'text': 'What does f of n minus 1 signify?', 'start': 457.328, 'duration': 1.901}, {'end': 471.431, 'text': 'Minimum energy required to reach n minus 1 from zero index?', 'start': 459.909, 'duration': 11.522}, {'end': 473.732, 'text': 'that is what the recursion will signify.', 'start': 471.431, 'duration': 2.301}, {'end': 476.593, 'text': 'can i can i express the recursion in terms of index?', 'start': 473.732, 'duration': 2.861}, {'end': 477.673, 'text': "that's my first step.", 'start': 476.593, 'duration': 1.08}, {'end': 479.934, 'text': "i'd like yes, you can how.", 'start': 477.673, 'duration': 2.261}, {'end': 481.234, 'text': 'there are array indexes.', 'start': 479.934, 'duration': 1.3}, {'end': 483.734, 'text': 'there are array indexes till n minus one.', 'start': 481.234, 'duration': 2.5}, {'end': 487.375, 'text': "so i'll consider every array index as an index.", 'start': 483.734, 'duration': 3.641}, {'end': 489.376, 'text': "so okay, that's fine.", 'start': 487.375, 'duration': 2.001}, {'end': 491.817, 'text': "so i can be like okay, that's, that's absolutely fine.", 'start': 489.376, 'duration': 2.441}, {'end': 493.117, 'text': "so let's do it.", 'start': 491.817, 'duration': 1.3}, {'end': 495.998, 'text': 'so can i say, uh, what will be f of zero?', 'start': 493.117, 'duration': 2.881}, {'end': 501.763, 'text': 'like common sense, What will be the costing in order to reach from 0 to 0?', 'start': 495.998, 'duration': 5.765}, {'end': 503.184, 'text': "That's going to be 0..", 'start': 501.763, 'duration': 1.421}, {'end': 508.129, 'text': 'Because f of n minus 1 was stating the costing from n minus 1 to 0.', 'start': 503.184, 'duration': 4.945}, {'end': 511.493, 'text': 'So, in order to reach 0 to 0, the costing will be 0.', 'start': 508.129, 'duration': 3.364}, {'end': 512.634, 'text': 'So, I know one thing for sure.', 'start': 511.493, 'duration': 1.141}, {'end': 516.378, 'text': 'That the costing for this guy will be 0.', 'start': 513.054, 'duration': 3.324}, {'end': 517.078, 'text': 'No matter what you do.', 'start': 516.378, 'duration': 0.7}, {'end': 518.62, 'text': 'No matter what you do.', 'start': 517.98, 'duration': 0.64}, {'end': 521.33, 'text': "Now, let's so.", 'start': 519.441, 'duration': 1.889}, {'end': 523.03, 'text': 'we have figured out what is the index.', 'start': 521.33, 'duration': 1.7}, {'end': 524.312, 'text': 'that will be the air index.', 'start': 523.03, 'duration': 1.282}, {'end': 527.693, 'text': 'next thing is do all stuffs on that index.', 'start': 524.312, 'duration': 3.381}, {'end': 530.454, 'text': 'yes, do all stuffs on that index.', 'start': 527.693, 'duration': 2.761}, {'end': 532.515, 'text': 'now, what is what?', 'start': 530.454, 'duration': 2.061}, {'end': 532.875, 'text': 'what i?', 'start': 532.515, 'duration': 0.36}, {'end': 534.516, 'text': 'what is the frog allowed to do?', 'start': 532.875, 'duration': 1.641}, {'end': 539.017, 'text': 'the frog is allowed to either jump plus one or to either jump plus two.', 'start': 534.516, 'duration': 4.501}, {'end': 539.838, 'text': "so why don't you do that?", 'start': 539.017, 'duration': 0.821}, {'end': 542.32, 'text': 'do all stuffs on that index.', 'start': 540.678, 'duration': 1.642}, {'end': 543.741, 'text': 'please do it.', 'start': 542.32, 'duration': 1.421}, {'end': 548.185, 'text': 'so what you will do is you will say okay, i will do all stuffs on that index.', 'start': 543.741, 'duration': 4.444}, {'end': 553.73, 'text': 'so if i do a single jump like, i can say it as the left recursion.', 'start': 548.185, 'duration': 5.545}, {'end': 557.193, 'text': 'so the single jump will say f of index minus one.', 'start': 553.73, 'duration': 3.463}, {'end': 562.197, 'text': "i'm doing this, but if i'm jumping, yes, the question arises.", 'start': 557.193, 'duration': 5.004}, {'end': 569.903, 'text': "if i'm jumping from an index to an index minus one, what is the energy that is being consumed?", 'start': 562.197, 'duration': 7.706}, {'end': 579.891, 'text': 'i know, in order to jump from index to index minus one, the energy consumed is array of index minus, array of index minus one.', 'start': 569.903, 'duration': 9.988}, {'end': 582.213, 'text': 'that is what the energy is consumed.', 'start': 579.891, 'duration': 2.322}, {'end': 588.418, 'text': 'can i say this is what the energy will be consumed to jump from index to index minus one.', 'start': 582.213, 'duration': 6.205}, {'end': 589.919, 'text': 'and then i can ask the recursion.', 'start': 588.418, 'duration': 1.501}, {'end': 593.581, 'text': 'hey, recursion, i have reached index minus one.', 'start': 589.919, 'duration': 3.662}, {'end': 599.104, 'text': "now it's your job to tell me from index minus one to zero, how much it will cost you.", 'start': 593.581, 'duration': 5.523}, {'end': 600.565, 'text': 'recursion will do the job.', 'start': 599.104, 'duration': 1.461}, {'end': 607.309, 'text': "i'll ask the recursion to tell what will be the costing from index minus one to zero, because i know the costing from index to index minus one.", 'start': 600.565, 'duration': 6.744}, {'end': 608.469, 'text': "i've taken that.", 'start': 607.309, 'duration': 1.16}], 'summary': 'The transcript discusses recursion and minimum energy required for reaching indexes, with a focus on index manipulation.', 'duration': 32.453, 'max_score': 417.71, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ417710.jpg'}, {'end': 511.493, 'src': 'embed', 'start': 481.234, 'weight': 3, 'content': [{'end': 483.734, 'text': 'there are array indexes till n minus one.', 'start': 481.234, 'duration': 2.5}, {'end': 487.375, 'text': "so i'll consider every array index as an index.", 'start': 483.734, 'duration': 3.641}, {'end': 489.376, 'text': "so okay, that's fine.", 'start': 487.375, 'duration': 2.001}, {'end': 491.817, 'text': "so i can be like okay, that's, that's absolutely fine.", 'start': 489.376, 'duration': 2.441}, {'end': 493.117, 'text': "so let's do it.", 'start': 491.817, 'duration': 1.3}, {'end': 495.998, 'text': 'so can i say, uh, what will be f of zero?', 'start': 493.117, 'duration': 2.881}, {'end': 501.763, 'text': 'like common sense, What will be the costing in order to reach from 0 to 0?', 'start': 495.998, 'duration': 5.765}, {'end': 503.184, 'text': "That's going to be 0..", 'start': 501.763, 'duration': 1.421}, {'end': 508.129, 'text': 'Because f of n minus 1 was stating the costing from n minus 1 to 0.', 'start': 503.184, 'duration': 4.945}, {'end': 511.493, 'text': 'So, in order to reach 0 to 0, the costing will be 0.', 'start': 508.129, 'duration': 3.364}], 'summary': 'Explaining array indexes and calculating cost from 0 to 0 as 0.', 'duration': 30.259, 'max_score': 481.234, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ481234.jpg'}, {'end': 582.213, 'src': 'embed', 'start': 557.193, 'weight': 2, 'content': [{'end': 562.197, 'text': "i'm doing this, but if i'm jumping, yes, the question arises.", 'start': 557.193, 'duration': 5.004}, {'end': 569.903, 'text': "if i'm jumping from an index to an index minus one, what is the energy that is being consumed?", 'start': 562.197, 'duration': 7.706}, {'end': 579.891, 'text': 'i know, in order to jump from index to index minus one, the energy consumed is array of index minus, array of index minus one.', 'start': 569.903, 'duration': 9.988}, {'end': 582.213, 'text': 'that is what the energy is consumed.', 'start': 579.891, 'duration': 2.322}], 'summary': 'Jumping from index to index minus one consumes the energy of array[index] - array[index-1].', 'duration': 25.02, 'max_score': 557.193, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ557193.jpg'}, {'end': 690.948, 'src': 'embed', 'start': 647.687, 'weight': 1, 'content': [{'end': 655.73, 'text': 'so you need to write a case like this if index is greater than one, then only i can take the right jump.', 'start': 647.687, 'duration': 8.043}, {'end': 661.292, 'text': "otherwise i cannot like make sense, because if you add the first index you'll not be able to take the right job.", 'start': 655.73, 'duration': 5.562}, {'end': 663.293, 'text': 'so that is absolutely making sense.', 'start': 661.292, 'duration': 2.001}, {'end': 665.834, 'text': "so i'm like, okay, fine, that's fine.", 'start': 663.293, 'duration': 2.541}, {'end': 667.115, 'text': "now what's the next step?", 'start': 665.834, 'duration': 1.281}, {'end': 672.135, 'text': 'take the minimal, because the question stated minimum energy.', 'start': 668.592, 'duration': 3.543}, {'end': 674.556, 'text': 'had the question stated maximum energy, you would have done it.', 'start': 672.135, 'duration': 2.421}, {'end': 676.798, 'text': 'had the question stated something else, you would have done it.', 'start': 674.556, 'duration': 2.242}, {'end': 680.24, 'text': 'but in this the question stated find the minimum energy.', 'start': 676.798, 'duration': 3.442}, {'end': 685.324, 'text': 'so there is a way in which you jumped from index to index minus one.', 'start': 680.24, 'duration': 5.084}, {'end': 690.948, 'text': "there's a way in which you jump from index to index minus two and ask the recursion to find out the remaining answer.", 'start': 685.324, 'duration': 5.624}], 'summary': 'To find minimum energy, use recursion to jump from index to index minus one or index minus two.', 'duration': 43.261, 'max_score': 647.687, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ647687.jpg'}], 'start': 391.319, 'title': 'Recursion and energy recurrence', 'summary': 'Covers the use of recursion to find the minimum energy path and explains the minimum energy recurrence relationship, providing step-by-step explanations and emphasizing problem-solving steps.', 'chapters': [{'end': 534.516, 'start': 391.319, 'title': 'Recursion for finding minimum energy path', 'summary': 'Discusses the use of recursion to find the minimum energy path, emphasizing the steps of expressing the problem in terms of index, performing operations on the index, and calculating the minimum energy required.', 'duration': 143.197, 'highlights': ['The first step is to express the problem in terms of index, considering every array index as an index and starting with f(0) as 0, signifying the cost to reach from 0 to 0.', 'Performing all operations on the index is essential for writing the recursion, ensuring that all possible ways are considered to find the minimum energy path.', 'Calculating the minimal of all operations to find the minimum energy required is crucial in writing the recursion to determine the path with the minimum energy.']}, {'end': 716.47, 'start': 534.516, 'title': 'Minimum energy recurrence relationship', 'summary': 'Explains the minimum energy recurrence relationship for jumping from an index to index minus one or index minus two, with considerations for energy consumption and minimal costing, providing a step-by-step explanation of the process.', 'duration': 181.954, 'highlights': ['The recursion to find out the remaining answer involves returning the minimal of left and right, as it is necessary to find the minimum energy for jumping from index to index minus one or index minus two.', 'The energy consumed to jump from index to index minus one is array of index minus array of index minus one, and for jumping from index to index minus two, it is a of index minus a of index minus two.', 'The chapter emphasizes the need to write a case to consider whether an index is greater than one before taking the right jump, as it is not possible to jump two if standing at the first index.']}], 'duration': 325.151, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ391319.jpg', 'highlights': ['Performing all operations on the index is essential for writing the recursion, ensuring that all possible ways are considered to find the minimum energy path.', 'The recursion to find out the remaining answer involves returning the minimal of left and right, as it is necessary to find the minimum energy for jumping from index to index minus one or index minus two.', 'The energy consumed to jump from index to index minus one is array of index minus array of index minus one, and for jumping from index to index minus two, it is a of index minus a of index minus two.', 'The first step is to express the problem in terms of index, considering every array index as an index and starting with f(0) as 0, signifying the cost to reach from 0 to 0.', 'Calculating the minimal of all operations to find the minimum energy required is crucial in writing the recursion to determine the path with the minimum energy.', 'The chapter emphasizes the need to write a case to consider whether an index is greater than one before taking the right jump, as it is not possible to jump two if standing at the first index.']}, {'end': 1540.868, 'segs': [{'end': 788.813, 'src': 'embed', 'start': 716.47, 'weight': 0, 'content': [{'end': 721.811, 'text': "now it's time to see if there are overlapping sub problems and how is this recursion actually working right?", 'start': 716.47, 'duration': 5.341}, {'end': 722.811, 'text': 'so we know.', 'start': 721.811, 'duration': 1}, {'end': 728.57, 'text': "we know we are at F of 5, because if I write down the indexes, it's like 0, 1, 2, 3, 4, 5.", 'start': 722.811, 'duration': 5.759}, {'end': 730.094, 'text': 'So we know we are at f of 5..', 'start': 728.573, 'duration': 1.521}, {'end': 739.561, 'text': 'Now, at f of 5, where can we go? We know that either we can take a jump to f of 4 or either we can take a jump to f of 3.', 'start': 730.094, 'duration': 9.467}, {'end': 741.062, 'text': "That's definitely known to us.", 'start': 739.561, 'duration': 1.501}, {'end': 742.924, 'text': 'So I can be like okay.', 'start': 741.463, 'duration': 1.461}, {'end': 752.411, 'text': "if I'm at f of 5 and there's this recursion call, then the left recursion will be like okay f of 4 plus absolute, of whatever height there is.", 'start': 742.924, 'duration': 9.487}, {'end': 754.552, 'text': 'So, what is the height? 60 minus 50.', 'start': 752.771, 'duration': 1.781}, {'end': 756.914, 'text': "There's this height of absolute 10.", 'start': 754.552, 'duration': 2.362}, {'end': 765.6, 'text': "and then there's a recursion of right, which is f of three plus again, and height difference of, uh, these couple of guys, which is three and five,", 'start': 756.914, 'duration': 8.686}, {'end': 767.801, 'text': 'ten minus fifty is forty.', 'start': 765.6, 'duration': 2.201}, {'end': 770.363, 'text': 'so you can be like absolute of forty.', 'start': 767.801, 'duration': 2.562}, {'end': 776.246, 'text': 'now, at first, this recursion will go, come back, and then this will go and come back.', 'start': 770.363, 'duration': 5.883}, {'end': 778.348, 'text': "then you'll return the minimum of these right.", 'start': 776.246, 'duration': 2.102}, {'end': 780.149, 'text': 'this is how the recursion is actually working.', 'start': 778.348, 'duration': 1.801}, {'end': 782.17, 'text': "so that's how i'm drawing the recursion tree.", 'start': 780.149, 'duration': 2.021}, {'end': 784.591, 'text': 'so f of four will say f of three and f of two.', 'start': 782.17, 'duration': 2.421}, {'end': 788.813, 'text': 'f of 3 will say f of 2 and f of 1.', 'start': 785.712, 'duration': 3.101}], 'summary': 'Analyzing recursion and overlapping subproblems in a dynamic programming context.', 'duration': 72.343, 'max_score': 716.47, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ716470.jpg'}, {'end': 859.793, 'src': 'embed', 'start': 811.468, 'weight': 1, 'content': [{'end': 819.831, 'text': "so i have figured out if if f of three answer, if f of three's answer, i'm figuring out, then f of three's answer, why will i again figure out?", 'start': 811.468, 'duration': 8.363}, {'end': 821.752, 'text': 'so there are overlapping sub problems.', 'start': 819.831, 'duration': 1.921}, {'end': 827.354, 'text': 'so if there are overlapping sub problems, can i say the answer to those problems will be similar.', 'start': 821.752, 'duration': 5.602}, {'end': 832.096, 'text': 'thereby i can apply memoization to this particular recursion got it.', 'start': 827.354, 'duration': 4.742}, {'end': 833.137, 'text': 'so i am understanding that.', 'start': 832.096, 'duration': 1.041}, {'end': 835.678, 'text': 'okay, i can definitely apply memoization.', 'start': 833.137, 'duration': 2.541}, {'end': 838.32, 'text': 'so you can easily apply migration.', 'start': 835.678, 'duration': 2.642}, {'end': 841.543, 'text': "but i just in case to complete the recursion, i'll quickly draw it.", 'start': 838.32, 'duration': 3.223}, {'end': 845.166, 'text': "so, in order to reach zero, i'll take zero amount, correct?", 'start': 841.543, 'duration': 3.623}, {'end': 846.407, 'text': 'so f of one.', 'start': 845.166, 'duration': 1.241}, {'end': 848.649, 'text': 'what would have what it would have done?', 'start': 846.407, 'duration': 2.242}, {'end': 851.732, 'text': 'ideally in f of one was this recursion.', 'start': 848.649, 'duration': 3.083}, {'end': 859.793, 'text': 'so f of one went and there was a left recursion call of f of 0, plus the jump from 1 to 0.', 'start': 851.732, 'duration': 8.061}], 'summary': 'Identifying overlapping subproblems to apply memoization for recursion.', 'duration': 48.325, 'max_score': 811.468, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ811468.jpg'}, {'end': 910.318, 'src': 'heatmap', 'start': 861.575, 'weight': 0.744, 'content': [{'end': 864.138, 'text': 'a jump from 1 to 0, so absolute of something.', 'start': 861.575, 'duration': 2.563}, {'end': 867.403, 'text': "let's see, 1 to 0 will cost you 20..", 'start': 864.138, 'duration': 3.265}, {'end': 870.253, 'text': 'so you can add a 20.', 'start': 867.403, 'duration': 2.85}, {'end': 877.175, 'text': 'about the right recursion, can i say uh, since we are standing at the first index, there will be no right recursion because you cannot jump.', 'start': 870.253, 'duration': 6.922}, {'end': 878.135, 'text': 'couple of index.', 'start': 877.175, 'duration': 0.96}, {'end': 881.096, 'text': 'so i can say right is probably some bigger value.', 'start': 878.135, 'duration': 2.961}, {'end': 883.657, 'text': 'now, f of 0 will return you 0.', 'start': 881.096, 'duration': 2.561}, {'end': 885.998, 'text': 'for sure, this will return you 0..', 'start': 883.657, 'duration': 2.341}, {'end': 889.639, 'text': 'so the left took 20 and the right took 20.', 'start': 885.998, 'duration': 3.641}, {'end': 891.379, 'text': 'so what will you return?', 'start': 889.639, 'duration': 1.74}, {'end': 894.88, 'text': 'you return the minimum of both of them, which is 20 comma.', 'start': 891.379, 'duration': 3.501}, {'end': 898.101, 'text': "let's assume this to be some intermax max.", 'start': 894.88, 'duration': 3.221}, {'end': 903.448, 'text': "so it's 20 what you return as f of 1..", 'start': 898.101, 'duration': 5.347}, {'end': 910.318, 'text': "Again, makes sense because if you're standing at f of 1, what is the cost that you'll take from 1 to 0? That's one way.", 'start': 903.448, 'duration': 6.87}], 'summary': 'Cost of jumping from 1 to 0 is 20, f(0) returns 0, f(1) returns 20.', 'duration': 48.743, 'max_score': 861.575, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ861575.jpg'}, {'end': 1283.005, 'src': 'heatmap', 'start': 1234.969, 'weight': 0.862, 'content': [{'end': 1237.09, 'text': 'Yes Look at the parameters changing.', 'start': 1234.969, 'duration': 2.121}, {'end': 1240.051, 'text': 'Like, which parameters are changing? Just look at them.', 'start': 1237.11, 'duration': 2.941}, {'end': 1243.385, 'text': 'be like striver.', 'start': 1242.005, 'duration': 1.38}, {'end': 1247.366, 'text': 'there is only one parameter changing, which is the one parameter.', 'start': 1243.385, 'duration': 3.981}, {'end': 1248.707, 'text': "let's come back.", 'start': 1247.366, 'duration': 1.341}, {'end': 1250.187, 'text': "it's index.", 'start': 1248.707, 'duration': 1.48}, {'end': 1251.507, 'text': 'what is the maximum value of index?', 'start': 1250.187, 'duration': 1.32}, {'end': 1253.008, 'text': "let's look at the recursion tree.", 'start': 1251.507, 'duration': 1.501}, {'end': 1258.869, 'text': "five. so you'll require a six size array, because in a six size array there will be index five.", 'start': 1253.008, 'duration': 5.861}, {'end': 1265.551, 'text': 'so you can definitely create a dp size of six over here, which is indirectly dp of n plus one.', 'start': 1258.869, 'duration': 6.682}, {'end': 1267.531, 'text': 'remember three steps.', 'start': 1265.551, 'duration': 1.98}, {'end': 1271.192, 'text': 'step one is this declare an array of size n plus one.', 'start': 1267.531, 'duration': 3.661}, {'end': 1274.282, 'text': 'step two Before returning, add it up.', 'start': 1271.192, 'duration': 3.09}, {'end': 1276.843, 'text': 'DP of index.', 'start': 1275.862, 'duration': 0.981}, {'end': 1278.123, 'text': 'Before returning, add it up.', 'start': 1276.903, 'duration': 1.22}, {'end': 1279.624, 'text': 'Store it and return.', 'start': 1278.803, 'duration': 0.821}, {'end': 1283.005, 'text': 'Step So, this is step 2.', 'start': 1280.324, 'duration': 2.681}], 'summary': 'Parameters changing, maximum index value, recursion tree, array size, steps for creating dp of n plus one.', 'duration': 48.036, 'max_score': 1234.969, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ1234969.jpg'}], 'start': 716.47, 'title': 'Recursion and memoization in dynamic programming', 'summary': 'Explores recursion in dynamic programming, delving into recursion tree, f of 5 subproblems, and height differences, then discusses optimizing recursion with memoization, exemplifying minimal cost calculation with a time complexity of o(n).', 'chapters': [{'end': 788.813, 'start': 716.47, 'title': 'Recursion in dynamic programming', 'summary': 'Explains the recursion tree and how the recursion works in dynamic programming, using the example of solving f of 5 with its subproblems f of 4 and f of 3, and discusses the height differences and absolute values involved in the recursion.', 'duration': 72.343, 'highlights': ['The recursion tree is drawn to illustrate how the recursion works, with F of 5 leading to subproblems F of 4 and F of 3, and the return of the minimum value.', 'Detailed explanation of the recursion process involving the height differences and absolute values, for example, the height difference of 60 - 50 leading to an absolute value of 10, and 10 - 50 resulting in an absolute value of 40.', 'Explanation of the subproblems and their recursive calls, such as F of 5 leading to F of 4 and F of 3, and F of 3 leading to F of 2 and F of 1.']}, {'end': 1540.868, 'start': 788.813, 'title': 'Optimizing recursion with memoization', 'summary': 'Discusses optimizing a recursive solution using memoization to solve overlapping subproblems in a dynamic programming context, demonstrating the process through an example of calculating the minimal cost for a set of jumps, culminating in a time complexity of o(n).', 'duration': 752.055, 'highlights': ['The chapter discusses the process of identifying and applying memoization to optimize a recursive solution, demonstrating the concept through an example of calculating the minimal cost for a set of jumps, with the final time complexity being O(n).', 'The speaker explains the process of identifying overlapping subproblems in the recursive solution and how applying memoization can significantly reduce the number of redundant computations, improving time complexity to O(n).', 'The detailed explanation of converting a recursive solution into a dynamic programming solution using memoization, resulting in a significant reduction in time complexity to O(n).', 'The step-by-step process of converting a recursive solution into a dynamic programming solution using memoization, resulting in a substantial improvement in time complexity to O(n).', 'The demonstration of implementing memoization to optimize a recursive solution, resulting in a notable reduction in time complexity to O(n) for solving the given problem.']}], 'duration': 824.398, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ716470.jpg', 'highlights': ['The recursion tree is drawn to illustrate how the recursion works, with F of 5 leading to subproblems F of 4 and F of 3, and the return of the minimum value.', 'The chapter discusses the process of identifying and applying memoization to optimize a recursive solution, demonstrating the concept through an example of calculating the minimal cost for a set of jumps, with the final time complexity being O(n).', 'Detailed explanation of the recursion process involving the height differences and absolute values, for example, the height difference of 60 - 50 leading to an absolute value of 10, and 10 - 50 resulting in an absolute value of 40.', 'The speaker explains the process of identifying overlapping subproblems in the recursive solution and how applying memoization can significantly reduce the number of redundant computations, improving time complexity to O(n).', 'Explanation of the subproblems and their recursive calls, such as F of 5 leading to F of 4 and F of 3, and F of 3 leading to F of 2 and F of 1.']}, {'end': 1855.952, 'segs': [{'end': 1568.264, 'src': 'embed', 'start': 1540.868, 'weight': 0, 'content': [{'end': 1546.149, 'text': "so, in the first lecture, i told you, after memoization, it's very important to understand.", 'start': 1540.868, 'duration': 5.281}, {'end': 1551.651, 'text': 'how do we do the tabulation one and after that we will do the space optimization.', 'start': 1546.149, 'duration': 5.502}, {'end': 1553.631, 'text': 'what is memoization?', 'start': 1551.651, 'duration': 1.98}, {'end': 1556.692, 'text': "top down, why, let's understand.", 'start': 1553.631, 'duration': 3.061}, {'end': 1559.673, 'text': 'so in the recursion, if you observe, what did you do?', 'start': 1556.692, 'duration': 2.981}, {'end': 1568.264, 'text': 'you had a top portion, but first the down answers, like you, went from top to down, correct, what is tabulation?', 'start': 1560.68, 'duration': 7.584}], 'summary': 'The lecture covers memoization, tabulation, and recursion in understanding algorithms.', 'duration': 27.396, 'max_score': 1540.868, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ1540868.jpg'}, {'end': 1734.476, 'src': 'heatmap', 'start': 1588.583, 'weight': 2, 'content': [{'end': 1593.144, 'text': "you'll take zero, you'll fill one, then you'll fill two, then you'll fill three, then you'll fill four, you'll fill five,", 'start': 1588.583, 'duration': 4.561}, {'end': 1594.424, 'text': "you'll go from the bottom to the.", 'start': 1593.144, 'duration': 1.28}, {'end': 1598.405, 'text': "so that's tabulation, understood.", 'start': 1594.424, 'duration': 3.981}, {'end': 1601.265, 'text': 'now, what did i tell you in tabulation?', 'start': 1598.405, 'duration': 2.86}, {'end': 1602.685, 'text': "what's the first step?", 'start': 1601.265, 'duration': 1.42}, {'end': 1608.066, 'text': 'step one is to see in memoization, how much dp array did you use?', 'start': 1602.685, 'duration': 5.381}, {'end': 1613.041, 'text': 'we know we used a dp array of size n plus one.', 'start': 1608.066, 'duration': 4.975}, {'end': 1617.943, 'text': 'so just without thinking anything, uh, you can initialize that.', 'start': 1613.041, 'duration': 4.902}, {'end': 1621.245, 'text': 'okay, so without thinking anything, you can initialize that, by the way.', 'start': 1617.943, 'duration': 3.302}, {'end': 1622.825, 'text': 'uh, it will be n like.', 'start': 1621.245, 'duration': 1.58}, {'end': 1626.527, 'text': 'even if you initialize n, it will work, because we have used a zero based indexing.', 'start': 1622.825, 'duration': 3.702}, {'end': 1629.728, 'text': 'so make sure everything is initialized with minus one.', 'start': 1626.527, 'duration': 3.201}, {'end': 1632.709, 'text': "or you can initialize that with zero, doesn't matter over here.", 'start': 1629.728, 'duration': 2.981}, {'end': 1634.33, 'text': 'so first thing is done.', 'start': 1632.709, 'duration': 1.621}, {'end': 1634.85, 'text': "what's the next step?", 'start': 1634.33, 'duration': 0.52}, {'end': 1641.695, 'text': 'look for the base case, because in recursion it will stop down it over, hits down, top like bottom up.', 'start': 1635.908, 'duration': 5.787}, {'end': 1642.776, 'text': "so what's the base case?", 'start': 1641.695, 'duration': 1.081}, {'end': 1644.518, 'text': "let's look at the base case.", 'start': 1642.776, 'duration': 1.742}, {'end': 1651.345, 'text': 'states index equal to equal to zero, returns zero index equal to equal to zero, index equal to equal to zero.', 'start': 1644.518, 'duration': 6.827}, {'end': 1655.79, 'text': "so whatever is that, you'll write that dp of zero is equal to zero.", 'start': 1651.345, 'duration': 4.445}, {'end': 1656.231, 'text': 'just write it.', 'start': 1655.79, 'duration': 0.441}, {'end': 1659.617, 'text': 'after that, just look at the recursion.', 'start': 1657.196, 'duration': 2.421}, {'end': 1663.199, 'text': 'state these lines when will it be executed?', 'start': 1659.617, 'duration': 3.582}, {'end': 1671.562, 'text': 'i can be like it will be executed at one, two, three, four and so on till n minus one of the index makes sense, because the worst call,', 'start': 1663.199, 'duration': 8.363}, {'end': 1673.723, 'text': "worst call that i'll make will be n minus one.", 'start': 1671.562, 'duration': 2.161}, {'end': 1676.324, 'text': 'so it will be executed for sure.', 'start': 1673.723, 'duration': 2.601}, {'end': 1681.686, 'text': "i'm like yes, so please write it i equal to one till n minus one.", 'start': 1676.324, 'duration': 5.362}, {'end': 1683.427, 'text': 'run a for loop, perfect.', 'start': 1681.686, 'duration': 1.741}, {'end': 1685.242, 'text': "What's the next step?", 'start': 1684.502, 'duration': 0.74}, {'end': 1687.183, 'text': 'Just go and look at the recursion.', 'start': 1685.963, 'duration': 1.22}, {'end': 1693.846, 'text': "What am I doing? What's the stuff done on the index? Yes.", 'start': 1687.383, 'duration': 6.463}, {'end': 1696.648, 'text': 'Replace this with dp and write it.', 'start': 1694.687, 'duration': 1.961}, {'end': 1698.989, 'text': 'So, the first step is very simple.', 'start': 1697.188, 'duration': 1.801}, {'end': 1713.636, 'text': 'I can say if I take first step, it will be dp of index minus 1 plus absolute of array of index minus array of index minus 1.', 'start': 1700.57, 'duration': 13.066}, {'end': 1719.203, 'text': 'Simple, can say second step will only implicate if i is greater than one.', 'start': 1713.636, 'duration': 5.567}, {'end': 1721.125, 'text': 'remember super super.', 'start': 1719.203, 'duration': 1.922}, {'end': 1724.047, 'text': "second step will only implement if that's true.", 'start': 1721.125, 'duration': 2.922}, {'end': 1732.895, 'text': 'so dp of index minus two plus absolute of a of index minus a of index minus two.', 'start': 1724.047, 'duration': 8.848}, {'end': 1734.476, 'text': 'as simple as it gets.', 'start': 1732.895, 'duration': 1.581}], 'summary': 'Explanation of tabulation and memoization for dp array initialization and base case handling.', 'duration': 145.893, 'max_score': 1588.583, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ1588583.jpg'}, {'end': 1671.562, 'src': 'embed', 'start': 1634.33, 'weight': 3, 'content': [{'end': 1634.85, 'text': "what's the next step?", 'start': 1634.33, 'duration': 0.52}, {'end': 1641.695, 'text': 'look for the base case, because in recursion it will stop down it over, hits down, top like bottom up.', 'start': 1635.908, 'duration': 5.787}, {'end': 1642.776, 'text': "so what's the base case?", 'start': 1641.695, 'duration': 1.081}, {'end': 1644.518, 'text': "let's look at the base case.", 'start': 1642.776, 'duration': 1.742}, {'end': 1651.345, 'text': 'states index equal to equal to zero, returns zero index equal to equal to zero, index equal to equal to zero.', 'start': 1644.518, 'duration': 6.827}, {'end': 1655.79, 'text': "so whatever is that, you'll write that dp of zero is equal to zero.", 'start': 1651.345, 'duration': 4.445}, {'end': 1656.231, 'text': 'just write it.', 'start': 1655.79, 'duration': 0.441}, {'end': 1659.617, 'text': 'after that, just look at the recursion.', 'start': 1657.196, 'duration': 2.421}, {'end': 1663.199, 'text': 'state these lines when will it be executed?', 'start': 1659.617, 'duration': 3.582}, {'end': 1671.562, 'text': 'i can be like it will be executed at one, two, three, four and so on till n minus one of the index makes sense, because the worst call,', 'start': 1663.199, 'duration': 8.363}], 'summary': 'Identifying base case and recursion in a recursive function for dynamic programming.', 'duration': 37.232, 'max_score': 1634.33, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ1634330.jpg'}, {'end': 1787.998, 'src': 'heatmap', 'start': 1741.382, 'weight': 0.777, 'content': [{'end': 1752.118, 'text': 'dp of index will be minimum of DP of index minus.', 'start': 1741.382, 'duration': 10.736}, {'end': 1760.605, 'text': 'sorry, DP of first step and second step, as simple as it can get.', 'start': 1752.118, 'duration': 8.487}, {'end': 1764.688, 'text': "and if you write this, it's definitely going to work on this.", 'start': 1760.605, 'duration': 4.083}, {'end': 1773.956, 'text': "so I'll try to show you over here, like I'll just erase this and over here if I just write the same thing.", 'start': 1764.688, 'duration': 9.268}, {'end': 1787.998, 'text': "like you'll see over here, i try to write the same thing, like i'll write dp of 0 to be 0 for int i equal to 1 i lesser than n i plus plus.", 'start': 1773.956, 'duration': 14.042}], 'summary': 'The transcript discusses the concept of dynamic programming with a simple example.', 'duration': 46.616, 'max_score': 1741.382, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ1741382.jpg'}], 'start': 1540.868, 'title': 'Dynamic programming techniques', 'summary': 'Covers tabulation and space optimization in recursion, explaining the difference between memoization and tabulation, emphasizing the bottom-up approach of tabulation. it also explains the process of implementing memoization and tabulation in dynamic programming, with a focus on initializing the dp array, defining base cases, and ensuring efficiency by using minimum values and absolute differences for successful algorithm execution.', 'chapters': [{'end': 1588.583, 'start': 1540.868, 'title': 'Tabulation and space optimization in recursion', 'summary': 'Covers the concepts of tabulation and space optimization in recursion, explaining the difference between memoization and tabulation, and emphasizing the bottom-up approach of tabulation.', 'duration': 47.715, 'highlights': ['Tabulation is the opposite of memoization, involving a bottom-up approach, filling from the bottom to the top.', 'Understanding the concepts of memoization, tabulation, and space optimization is crucial for efficient recursion.', 'Recursion involves moving from top to down, while tabulation involves filling from the bottom to the top.']}, {'end': 1855.952, 'start': 1588.583, 'title': 'Memoization and tabulation in dynamic programming', 'summary': 'Explains the process of implementing memoization and tabulation in dynamic programming, with a focus on initializing the dp array, defining base cases, and implementing recursion through a for loop and conditional statements, ensuring efficiency by using minimum values and absolute differences, leading to successful execution of the algorithm.', 'duration': 267.369, 'highlights': ['The first step in implementing memoization and tabulation involves initializing the dp array, which is done by setting it to the size of n plus one, ensuring all elements are initialized with either -1 or 0.', 'Defining the base case is crucial in memoization and tabulation, with specific conditions such as index equal to zero, leading to setting dp of zero as equal to zero.', 'Implementing recursion involves iterating through a for loop from 1 to n minus one, with conditional statements for executing specific steps based on the value of i, which contributes to the efficient execution of the algorithm.', 'The process of recursion includes replacing specific calculations with dp values, such as the first step involving dp of index minus 1 plus the absolute difference of array elements, and the second step involving dp of index minus two plus the absolute difference of array elements, leading to the minimum value being stored as dp of index.']}], 'duration': 315.084, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ1540868.jpg', 'highlights': ['Tabulation is the opposite of memoization, involving a bottom-up approach, filling from the bottom to the top.', 'Understanding the concepts of memoization, tabulation, and space optimization is crucial for efficient recursion.', 'The first step in implementing memoization and tabulation involves initializing the dp array, which is done by setting it to the size of n plus one, ensuring all elements are initialized with either -1 or 0.', 'Defining the base case is crucial in memoization and tabulation, with specific conditions such as index equal to zero, leading to setting dp of zero as equal to zero.', 'Recursion involves moving from top to down, while tabulation involves filling from the bottom to the top.']}, {'end': 2320.361, 'segs': [{'end': 2001.508, 'src': 'embed', 'start': 1980.034, 'weight': 1, 'content': [{'end': 1988.88, 'text': "DP of I minus 2 will become this, right? So, do you need to carry an array? Can't I do this using couple of variables? Like, think.", 'start': 1980.034, 'duration': 8.846}, {'end': 1993.663, 'text': "Can't you do this using couple of variables? And the answer to that will be, yeah, I think we can.", 'start': 1989.44, 'duration': 4.223}, {'end': 2000.268, 'text': 'Because what we require at any particular instance I is the previous guy and the second previous guy.', 'start': 1993.743, 'duration': 6.525}, {'end': 2001.508, 'text': "I don't need anything more.", 'start': 2000.508, 'duration': 1}], 'summary': 'Using a couple of variables, dp of i minus 2 can be derived without needing an array.', 'duration': 21.474, 'max_score': 1980.034, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ1980034.jpg'}, {'end': 2121.954, 'src': 'heatmap', 'start': 2087.016, 'weight': 0.783, 'content': [{'end': 2098.702, 'text': 'and after that can I say in the next step the previous 2 will be previous and the previous will be nothing, but Cur I and this guy will be Cur I.', 'start': 2087.016, 'duration': 11.686}, {'end': 2099.084, 'text': 'Make sense?', 'start': 2098.702, 'duration': 0.382}, {'end': 2103.02, 'text': 'makes sense, and what will be the answer at the end?', 'start': 2099.918, 'duration': 3.102}, {'end': 2111.586, 'text': 'whenever you exceed, i will go beyond n minus 1 and whenever this for loop ends, the value of i will be n yes,', 'start': 2103.02, 'duration': 8.566}, {'end': 2121.954, 'text': 'the value of i will be over here and for this guy, for this guy previous will be at n minus 1 and you always required the answer of n minus 1.', 'start': 2111.586, 'duration': 10.368}], 'summary': 'The value of i will be n at the end, and the answer is always n minus 1.', 'duration': 34.938, 'max_score': 2087.016, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ2087016.jpg'}, {'end': 2165.847, 'src': 'embed', 'start': 2130.668, 'weight': 0, 'content': [{'end': 2138.233, 'text': "So if you do this, you will be able to get your space optimized and you'll no more be requiring a DP array.", 'start': 2130.668, 'duration': 7.565}, {'end': 2144.037, 'text': "So if I try to write this in the code, probably I'll delete this and I can keep a previous equal to zero.", 'start': 2138.633, 'duration': 5.404}, {'end': 2147.499, 'text': 'I can keep a previous two as well as zero.', 'start': 2144.497, 'duration': 3.002}, {'end': 2165.847, 'text': 'and i can just omit this to previous and i can just omit this to previous two and i can be like this to be cur i and i can see the previous two will become previous now and the previous guy will be,', 'start': 2148.983, 'duration': 16.864}], 'summary': 'Optimize space by removing the need for a dp array in the code.', 'duration': 35.179, 'max_score': 2130.668, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ2130668.jpg'}, {'end': 2227.869, 'src': 'embed', 'start': 2179.293, 'weight': 2, 'content': [{'end': 2184.577, 'text': "it works, let's submit and it's working fine.", 'start': 2179.293, 'duration': 5.284}, {'end': 2187.619, 'text': 'so we have done a space optimization.', 'start': 2184.577, 'duration': 3.042}, {'end': 2189.92, 'text': 'yes, we have done a space optimization.', 'start': 2187.619, 'duration': 2.301}, {'end': 2194.524, 'text': 'so this is how this problem can be easily solved.', 'start': 2189.92, 'duration': 4.604}, {'end': 2196.765, 'text': 'so this is how i can space optimize it.', 'start': 2194.524, 'duration': 2.241}, {'end': 2199.027, 'text': 'i hope you have understood the space optimization.', 'start': 2196.765, 'duration': 2.262}, {'end': 2201.949, 'text': "now there's a follow-up to this wonderful problem.", 'start': 2199.027, 'duration': 2.922}, {'end': 2209.084, 'text': 'okay, Now, this question stated you can jump to i plus 1 and you can jump to i plus 2..', 'start': 2201.949, 'duration': 7.135}, {'end': 2210.465, 'text': "That's the maximum that you put.", 'start': 2209.084, 'duration': 1.381}, {'end': 2214.586, 'text': 'Now, the follow-up states, the follow-up states, they can be k jumps.', 'start': 2211.165, 'duration': 3.421}, {'end': 2218.387, 'text': 'Yes, the follow-up states that they can be k jumps.', 'start': 2215.006, 'duration': 3.381}, {'end': 2227.189, 'text': 'Now, instead of i plus 1, you can jump to i plus 1, i plus 2, i plus 3 till i plus k.', 'start': 2218.407, 'duration': 8.782}, {'end': 2227.869, 'text': "That's what I'm saying.", 'start': 2227.189, 'duration': 0.68}], 'summary': 'Space optimization achieved, with the ability to make k jumps in follow-up.', 'duration': 48.576, 'max_score': 2179.293, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ2179293.jpg'}, {'end': 2304.012, 'src': 'embed', 'start': 2272.7, 'weight': 5, 'content': [{'end': 2277.662, 'text': "where i'll tell you how to change this problem slightly and you'll be able to do this problem for k jobs.", 'start': 2272.7, 'duration': 4.962}, {'end': 2282.323, 'text': "so, guys, if you have watched this video till now and if you've understood everything, you know what to do.", 'start': 2277.662, 'duration': 4.661}, {'end': 2285.784, 'text': "this is what i expect, even if you're very, very, very lazy.", 'start': 2282.323, 'duration': 3.461}, {'end': 2287.445, 'text': 'please comment us.', 'start': 2285.784, 'duration': 1.661}, {'end': 2292.106, 'text': 'us means understood, and this is something which you should always do.', 'start': 2287.445, 'duration': 4.661}, {'end': 2296.768, 'text': "you're watching these videos because it takes a hell lot of effort to make these kind of videos.", 'start': 2292.426, 'duration': 4.342}, {'end': 2304.012, 'text': "and yes, if you're new to this channel, please please do consider subscribing and please do share this channel among your college mates, friends,", 'start': 2296.768, 'duration': 7.244}], 'summary': 'Learn to solve problem for k jobs; encourage engagement and subscription.', 'duration': 31.312, 'max_score': 2272.7, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ2272700.jpg'}, {'end': 2320.361, 'src': 'embed', 'start': 2312.197, 'weight': 4, 'content': [{'end': 2314.078, 'text': 'go and check it out.', 'start': 2312.197, 'duration': 1.881}, {'end': 2316.819, 'text': "that's the ultimate resource for placements, man.", 'start': 2314.078, 'duration': 2.741}, {'end': 2320.361, 'text': "and yeah, with this, uh, let's wrap up this video and probably meet in the next one tomorrow.", 'start': 2316.819, 'duration': 3.542}], 'summary': "Ultimate resource for placements. let's meet in the next video tomorrow.", 'duration': 8.164, 'max_score': 2312.197, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ2312197.jpg'}], 'start': 1856.673, 'title': 'Dynamic programming and specialized jump problems', 'summary': 'Explains space optimization in dynamic programming, reducing space complexity for improved efficiency, and discusses a specialized problem requiring k jumps. viewers are encouraged to engage and access additional resources provided.', 'chapters': [{'end': 2201.949, 'start': 1856.673, 'title': 'Space optimization in dynamic programming', 'summary': 'Explains how to achieve space optimization in dynamic programming by using a couple of variables instead of an array, resulting in reduced space complexity and improved efficiency.', 'duration': 345.276, 'highlights': ['By using a couple of variables instead of an array, space complexity can be reduced, leading to improved efficiency.', "The technique involves utilizing two variables, 'previous' and 'previous2', to represent the previous and second previous values, eliminating the need for a DP array.", 'The approach results in space optimization and improved performance, as demonstrated by successfully solving a problem and achieving the desired outcome.']}, {'end': 2320.361, 'start': 2201.949, 'title': 'Problem with k jumps', 'summary': "Discusses a problem where one needs to solve it using k jumps instead of the usual i plus 1 or i plus 2 jumps, and the viewers are urged to comment 'us' if they understand the content and are encouraged to check out the sd sheet link in the description.", 'duration': 118.412, 'highlights': ["The problem discusses using k jumps instead of the usual i plus 1 or i plus 2 jumps, and the viewers are encouraged to comment 'us' if they understand the content.", 'Viewers are urged to check out the sd sheet link in the description, which is described as the ultimate resource for placements.', "The lecturer mentions a follow-up problem that will be discussed before starting lecture four and encourages viewers to comment 'us' if they understand the content."]}], 'duration': 463.688, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/EgG3jsGoPvQ/pics/EgG3jsGoPvQ1856673.jpg', 'highlights': ['By using a couple of variables instead of an array, space complexity can be reduced, leading to improved efficiency.', "The technique involves utilizing two variables, 'previous' and 'previous2', to represent the previous and second previous values, eliminating the need for a DP array.", 'The approach results in space optimization and improved performance, as demonstrated by successfully solving a problem and achieving the desired outcome.', "The problem discusses using k jumps instead of the usual i plus 1 or i plus 2 jumps, and the viewers are encouraged to comment 'us' if they understand the content.", 'Viewers are urged to check out the sd sheet link in the description, which is described as the ultimate resource for placements.', "The lecturer mentions a follow-up problem that will be discussed before starting lecture four and encourages viewers to comment 'us' if they understand the content."]}], 'highlights': ['The importance of exploring all possible ways and avoiding the loss of significant outcomes is highlighted as a reason for preferring a recursive approach over a greedy one.', 'The discussion explains why a greedy solution will not work for the energy minimization problem.', "The concept of greedy algorithms is explained using a frog's movement example, emphasizing the attempt to minimize energy and take the minimal possible jumps.", 'The recursion to find out the remaining answer involves returning the minimal of left and right, as it is necessary to find the minimum energy for jumping from index to index minus one or index minus two.', 'The first step is to express the problem in terms of index, considering every array index as an index and starting with f(0) as 0, signifying the cost to reach from 0 to 0.', 'The recursion tree is drawn to illustrate how the recursion works, with F of 5 leading to subproblems F of 4 and F of 3, and the return of the minimum value.', 'Tabulation is the opposite of memoization, involving a bottom-up approach, filling from the bottom to the top.', 'By using a couple of variables instead of an array, space complexity can be reduced, leading to improved efficiency.', "The technique involves utilizing two variables, 'previous' and 'previous2', to represent the previous and second previous values, eliminating the need for a DP array."]}