title
DP 10. Minimum Path Sum in Grid | Asked to me In Microsoft Internship Interview | DP on GRIDS

description
Lecture Notes/C++/Java Codes: https://takeuforward.org/data-structure/minimum-path-sum-in-a-grid-dp-10/ Problem Link: https://bit.ly/3q5sqfu Pre-req for this Series: https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9 a Make sure to join our telegram group for discussions: https://linktr.ee/takeUforward Full Playlist: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY In this video, we solve the problem Minimum Path sum which teaches you about path sum property in grids. 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 10. Minimum Path Sum in Grid | Asked to me In Microsoft Internship Interview | DP on GRIDS', 'heatmap': [{'end': 517.345, 'start': 499.325, 'weight': 0.714}, {'end': 766.507, 'start': 740.602, 'weight': 0.855}, {'end': 1207.77, 'start': 1183.527, 'weight': 0.715}, {'end': 1242.071, 'start': 1223.956, 'weight': 0.721}, {'end': 1370.105, 'start': 1341.707, 'weight': 0.839}], 'summary': 'Covers dynamic programming on grids, discussing minimal path sum, limitations of greedy algorithm, minimal cost path recursion, dynamic programming in grids with time complexity of n cross m, space complexity of n cross m, and recursion stack space of m minus 1 plus n minus 1, and minimization and tabulation in dynamic programming.', 'chapters': [{'end': 35.111, 'segs': [{'end': 45.757, 'src': 'embed', 'start': 18.762, 'weight': 0, 'content': [{'end': 23.244, 'text': "Okay, so if you're not following the playlist, man, you're missing on a lot of premium stuff.", 'start': 18.762, 'duration': 4.482}, {'end': 27.627, 'text': "Please make sure you follow the playlist because you're going to learn DP in the best possible way.", 'start': 23.745, 'duration': 3.882}, {'end': 35.111, 'text': "So, what is the problem? Today's problem will be on grids and that's minimum path sum.", 'start': 28.128, 'duration': 6.983}, {'end': 45.757, 'text': "So what is it saying? It's saying there's something like Ninja Land is a country in the shape of a 2D grid with n rows and n columns.", 'start': 35.672, 'duration': 10.085}], 'summary': "Follow the playlist to learn dp effectively. today's problem: minimum path sum in 2d grid.", 'duration': 26.995, 'max_score': 18.762, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ18762.jpg'}], 'start': 0.429, 'title': 'Dp on grids: minimum path sum', 'summary': 'Covers the third problem from dp on grids, emphasizing the importance of following the playlist for a comprehensive understanding of dp.', 'chapters': [{'end': 35.111, 'start': 0.429, 'title': 'Dp on grids: minimum path sum', 'summary': 'Covers the third problem from dp on grids, focusing on minimum path sum, emphasizing the importance of following the playlist for a comprehensive understanding of dp.', 'duration': 34.682, 'highlights': ['The problem discussed is the third problem from DP on grids, focusing on minimum path sum.', 'Emphasizes the importance of following the playlist for a comprehensive understanding of DP.']}], 'duration': 34.682, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ429.jpg', 'highlights': ['Emphasizes the importance of following the playlist for a comprehensive understanding of DP.', 'The problem discussed is the third problem from DP on grids, focusing on minimum path sum.']}, {'end': 298.199, 'segs': [{'end': 93.99, 'src': 'embed', 'start': 65.093, 'weight': 0, 'content': [{'end': 67.595, 'text': 'You need to tell the minimum sum of that path.', 'start': 65.093, 'duration': 2.502}, {'end': 73.121, 'text': 'So this question was actually asked to me in my Microsoft internship interview.', 'start': 68.076, 'duration': 5.045}, {'end': 74.603, 'text': "It's an amazing question.", 'start': 73.702, 'duration': 0.901}, {'end': 80.662, 'text': 'Basically, it states if you start on from here and you want to go here.', 'start': 75.779, 'duration': 4.883}, {'end': 82.782, 'text': 'So, basically 0, 0, 1, 2.', 'start': 80.682, 'duration': 2.1}, {'end': 90.588, 'text': 'So, if you just start on from 0, 0 and you want to reach the end which is 0, 2.', 'start': 82.783, 'duration': 7.805}, {'end': 93.99, 'text': 'What is the minimal that you will take? Now, there can be a lot of paths.', 'start': 90.588, 'duration': 3.402}], 'summary': 'Microsoft intern was asked to find minimum sum of a path from (0,0) to (0,2).', 'duration': 28.897, 'max_score': 65.093, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ65093.jpg'}, {'end': 195.427, 'src': 'embed', 'start': 169.615, 'weight': 1, 'content': [{'end': 174.078, 'text': "So why not greedy? That's a very, very good question that might be arising.", 'start': 169.615, 'duration': 4.463}, {'end': 180.102, 'text': 'So why not follow greedy? Why not follow greedy paths? Again, makes sense.', 'start': 174.358, 'duration': 5.744}, {'end': 181.383, 'text': 'Makes a lot of sense.', 'start': 180.662, 'duration': 0.721}, {'end': 188.425, 'text': "Why don't you follow a greedy path? Let's understand how generically you understand that a greedy has not to be followed.", 'start': 182.003, 'duration': 6.422}, {'end': 192.686, 'text': 'So imagine I give you a grid, rather something like this.', 'start': 189.025, 'duration': 3.661}, {'end': 195.427, 'text': 'Okay I give you a grid, something like this.', 'start': 192.746, 'duration': 2.681}], 'summary': 'Exploring the reasoning behind not following a greedy path in algorithmic problem-solving.', 'duration': 25.812, 'max_score': 169.615, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ169615.jpg'}], 'start': 35.672, 'title': 'Grid path and greedy algorithm', 'summary': 'Discusses finding minimal sum of a path in a 2d grid and explains limitations of greedy algorithm with non-uniform values, illustrated by an example where the minimal sum calculation is 21.', 'chapters': [{'end': 168.754, 'start': 35.672, 'title': 'Ninja land grid path', 'summary': 'Discusses finding the minimal sum of a path in a 2d grid from the top left to bottom right, based on cost associated with each point, with an example of the minimal sum calculation being 21.', 'duration': 133.082, 'highlights': ['The minimal sum of the path from the top left to bottom right in a 2D grid with cost associated with each point is illustrated with an example of the minimal sum being 21, based on the constraints of only being allowed to move in the bottom or right direction.', 'The question was asked in a Microsoft internship interview and involves finding the minimal sum of a path in a 2D grid from the top left to bottom right, with constraints of only being allowed to move in the bottom or right direction, with an example of the minimal sum calculation being 21.']}, {'end': 298.199, 'start': 169.615, 'title': 'Greedy algorithm limitations', 'summary': 'Explains the limitations of following a greedy algorithm using a grid example, where non-uniform values can significantly impact the cost of the path chosen, leading to suboptimal solutions and potential future negative effects.', 'duration': 128.584, 'highlights': ['Following a greedy path in a non-uniform grid can lead to suboptimal solutions, as the cost of the path may significantly rise due to non-uniformity, impacting future decisions.', 'Uniformity in values is essential for applying a greedy algorithm, as non-uniform values may lead to increased or decreased costs, affecting future outcomes.']}], 'duration': 262.527, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ35672.jpg', 'highlights': ['The question involves finding the minimal sum of a path in a 2D grid from top left to bottom right, with a minimal sum calculation of 21.', 'Following a greedy path in a non-uniform grid can lead to suboptimal solutions due to significant cost rise.']}, {'end': 748.206, 'segs': [{'end': 383.128, 'src': 'embed', 'start': 322.185, 'weight': 1, 'content': [{'end': 329.919, 'text': 'try out all paths And in those all paths, tell me the path.', 'start': 322.185, 'duration': 7.734}, {'end': 332.301, 'text': 'tell me the path which has minimal cost.', 'start': 329.919, 'duration': 2.382}, {'end': 338.325, 'text': 'So whenever I say all paths, what does that signify??', 'start': 334.442, 'duration': 3.883}, {'end': 340.266, 'text': 'What algorithm that says?', 'start': 338.725, 'duration': 1.541}, {'end': 348.231, 'text': 'That definitely says recursion, because recursion is something that tries out all possible paths, correct?', 'start': 340.906, 'duration': 7.325}, {'end': 352.425, 'text': 'so what are the rules of writing recurrence relationships?', 'start': 348.743, 'duration': 3.682}, {'end': 353.946, 'text': "three rules that i've taught you.", 'start': 352.425, 'duration': 1.521}, {'end': 355.086, 'text': 'what are the three rules?', 'start': 353.946, 'duration': 1.14}, {'end': 356.787, 'text': 'the reels are very simple.', 'start': 355.086, 'duration': 1.701}, {'end': 362.43, 'text': "express the recurrence in terms of indexes over here it's a 2d grid.", 'start': 356.787, 'duration': 5.643}, {'end': 368.374, 'text': 'so express the uh stuff in terms of rows and columns as ij.', 'start': 362.43, 'duration': 5.944}, {'end': 372.936, 'text': 'second, explore all paths.', 'start': 368.374, 'duration': 4.562}, {'end': 375.758, 'text': 'explore all paths.', 'start': 372.936, 'duration': 2.822}, {'end': 377.939, 'text': 'third, take the best.', 'start': 375.758, 'duration': 2.181}, {'end': 383.128, 'text': 'take the minimal path, as the question recommends, minimal maximum count whatever.', 'start': 378.746, 'duration': 4.382}], 'summary': 'Recursion explores all paths and selects minimal cost, following 3 rules for recurrence relationships.', 'duration': 60.943, 'max_score': 322.185, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ322185.jpg'}, {'end': 464.255, 'src': 'embed', 'start': 433.513, 'weight': 5, 'content': [{'end': 439.183, 'text': "What's your base case? Can I say the base case is quite simple, similar to the previous question that we did.", 'start': 433.513, 'duration': 5.67}, {'end': 445.056, 'text': 'If we reach our destination, yes, if we reach our destination, we can say that, okay, we have reached our destination.', 'start': 439.604, 'duration': 5.452}, {'end': 448.97, 'text': "Let's return the value stored at A of 0, 0.", 'start': 445.549, 'duration': 3.421}, {'end': 451.391, 'text': 'Because this is going to be a part of my path.', 'start': 448.97, 'duration': 2.421}, {'end': 452.051, 'text': "Let's understand.", 'start': 451.431, 'duration': 0.62}, {'end': 453.832, 'text': 'This guy will be a part of your path.', 'start': 452.431, 'duration': 1.401}, {'end': 457.293, 'text': "Don't you think? So, why don't you return this? Because this has to be added to the path.", 'start': 453.972, 'duration': 3.321}, {'end': 464.255, 'text': 'Correct? And what about the other stuffs? You know, this will be I lesser than 0 or J lesser than 0.', 'start': 457.813, 'duration': 6.442}], 'summary': 'Discussion on reaching the destination and values along the path.', 'duration': 30.742, 'max_score': 433.513, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ433513.jpg'}, {'end': 533.772, 'src': 'heatmap', 'start': 499.325, 'weight': 0.714, 'content': [{'end': 500.625, 'text': 'so what will you return?', 'start': 499.325, 'duration': 1.3}, {'end': 511.523, 'text': "generally? remember, if you're trying to find minimum paths, you'll try to return such a big value, such a big value such that when you add this big value,", 'start': 500.625, 'duration': 10.898}, {'end': 513.462, 'text': 'the path gets a maximum cost.', 'start': 511.523, 'duration': 1.939}, {'end': 517.345, 'text': 'path gets a maximum cost, and you never take this got it.', 'start': 513.462, 'duration': 3.883}, {'end': 519.145, 'text': "so i've written the base cases.", 'start': 517.345, 'duration': 1.8}, {'end': 523.746, 'text': 'step one is done of expressing in terms of indexes and writing the base cases.', 'start': 519.145, 'duration': 4.601}, {'end': 524.707, 'text': "what's the next step?", 'start': 523.746, 'duration': 0.961}, {'end': 533.772, 'text': "the next step is very simple if i go upwards or if i go leftwards, now can i say if i go upwards, The current element is what I'm saying.", 'start': 524.707, 'duration': 9.065}], 'summary': 'Discussing finding minimum paths and expressing in terms of indexes and base cases.', 'duration': 34.447, 'max_score': 499.325, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ499325.jpg'}, {'end': 692.891, 'src': 'embed', 'start': 645.828, 'weight': 0, 'content': [{'end': 648.549, 'text': "Similar Like you're moving from the bottom to the top.", 'start': 645.828, 'duration': 2.721}, {'end': 652.572, 'text': 'Again, the prerequisite is the DP8 lecture.', 'start': 649.07, 'duration': 3.502}, {'end': 654.173, 'text': "That's the first lecture of the grid.", 'start': 652.972, 'duration': 1.201}, {'end': 657.015, 'text': 'If you have not seen that, please go back and watch it.', 'start': 654.853, 'duration': 2.162}, {'end': 664.216, 'text': 'Okay, so we have seen in the previous lecture, like in the lecture 8, so please, please, please follow the playlist.', 'start': 657.853, 'duration': 6.363}, {'end': 675.142, 'text': 'We have seen in the lecture 8 that if the recursion is something like we are moving in the up and left, there will be overlapping subproblems.', 'start': 665.377, 'duration': 9.765}, {'end': 682.206, 'text': 'And if there will be overlapping subproblems, what can we apply? Memoization, correct.', 'start': 675.883, 'duration': 6.323}, {'end': 687.488, 'text': 'We can apply something as Memoiation.', 'start': 682.786, 'duration': 4.702}, {'end': 690.749, 'text': 'So how do you apply memoiation? Again, very simple trick.', 'start': 687.888, 'duration': 2.861}, {'end': 692.891, 'text': 'Very, very simple trick.', 'start': 691.41, 'duration': 1.481}], 'summary': 'Recursion with overlapping subproblems requires memoization for optimization.', 'duration': 47.063, 'max_score': 645.828, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ645828.jpg'}, {'end': 748.206, 'src': 'embed', 'start': 720.084, 'weight': 4, 'content': [{'end': 722.285, 'text': 'declare as minus 1.', 'start': 720.084, 'duration': 2.201}, {'end': 724.167, 'text': 'so declare it as minus 1.', 'start': 722.285, 'duration': 1.882}, {'end': 737, 'text': 'after that, right before the result, store it and return, and before Before calling the recursion, if that state has been previously visited,', 'start': 724.167, 'duration': 12.833}, {'end': 739.761, 'text': "why don't you return that visited state??", 'start': 737, 'duration': 2.761}, {'end': 740.101, 'text': 'Yes,', 'start': 739.861, 'duration': 0.24}, {'end': 748.206, 'text': "Why don't you return that visited state? Step three, step one, step, sorry, step two, step three, and step one is the declaration.", 'start': 740.602, 'duration': 7.604}], 'summary': 'Declare -1, store before result, return visited state to optimize recursion', 'duration': 28.122, 'max_score': 720.084, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ720084.jpg'}], 'start': 298.199, 'title': 'Minimal and dynamic cost path', 'summary': 'Covers minimal cost path recursion and dynamic programming for finding the optimal path, emphasizing the importance of exploring all paths, writing recurrence relationships, and applying memoization to optimize the recursive function.', 'chapters': [{'end': 519.145, 'start': 298.199, 'title': 'Minimal cost path recursion', 'summary': 'Discusses the concept of finding the minimal cost path using recursion and explores the rules for writing recurrence relationships, emphasizing the importance of exploring all paths and selecting the minimal path.', 'duration': 220.946, 'highlights': ['The importance of exploring all paths in finding the minimal cost path is emphasized, with recursion being the algorithm that tries out all possible paths.', 'The three rules for writing recurrence relationships are outlined, which include expressing the recurrence in terms of indexes, exploring all paths, and selecting the minimal path.', 'The base case for the recursion is described, where reaching the destination returns the value stored at A of 0, 0 and handling cases where the recursion moves out of the boundary is explained.']}, {'end': 748.206, 'start': 519.145, 'title': 'Dynamic programming: up and left paths', 'summary': 'Discusses the process of finding minimal cost paths by moving upwards and leftwards in a grid, emphasizing the application of memoization for addressing overlapping subproblems, in order to optimize the recursive function, as part of the dynamic programming approach.', 'duration': 229.061, 'highlights': ['The process involves finding minimal cost paths in a grid by moving upwards and leftwards, addressing overlapping subproblems, and optimizing the recursive function using memoization.', 'The lecture emphasizes the importance of applying memoization to address overlapping subproblems and optimize the recursive function.', 'The lecture stresses the significance of watching the prerequisite DP8 lecture and following the playlist for comprehensive understanding.', 'The lecture details the step-by-step process of applying memoization for addressing overlapping subproblems and optimizing the recursive function.', 'The chapter highlights the significance of declaring values, applying memoization, and returning previously visited states as part of the dynamic programming approach.']}], 'duration': 450.007, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ298199.jpg', 'highlights': ['The process involves finding minimal cost paths in a grid by moving upwards and leftwards, addressing overlapping subproblems, and optimizing the recursive function using memoization.', 'The importance of exploring all paths in finding the minimal cost path is emphasized, with recursion being the algorithm that tries out all possible paths.', 'The three rules for writing recurrence relationships are outlined, which include expressing the recurrence in terms of indexes, exploring all paths, and selecting the minimal path.', 'The lecture emphasizes the importance of applying memoization to address overlapping subproblems and optimize the recursive function.', 'The chapter highlights the significance of declaring values, applying memoization, and returning previously visited states as part of the dynamic programming approach.', 'The base case for the recursion is described, where reaching the destination returns the value stored at A of 0, 0 and handling cases where the recursion moves out of the boundary is explained.', 'The lecture details the step-by-step process of applying memoization for addressing overlapping subproblems and optimizing the recursive function.', 'The lecture stresses the significance of watching the prerequisite DP8 lecture and following the playlist for comprehensive understanding.']}, {'end': 1057.036, 'segs': [{'end': 798.421, 'src': 'embed', 'start': 770.371, 'weight': 0, 'content': [{'end': 774.071, 'text': 'So the path length is this, m minus 1 plus n minus 1.', 'start': 770.371, 'duration': 3.7}, {'end': 774.892, 'text': 'Sublimation is done.', 'start': 774.071, 'duration': 0.821}, {'end': 778.775, 'text': 'What is the next step? Tabulation.', 'start': 775.652, 'duration': 3.123}, {'end': 782.418, 'text': 'We have to convert this into a tabulated solution.', 'start': 779.436, 'duration': 2.982}, {'end': 785.761, 'text': 'How do you do this? Again, quite straightforward.', 'start': 782.738, 'duration': 3.023}, {'end': 786.842, 'text': 'I have told you already.', 'start': 785.781, 'duration': 1.061}, {'end': 798.421, 'text': 'i and j two parameters where are the states from 0 to n minus 1 is what i will be j will be from 0 to m minus 1.', 'start': 789.031, 'duration': 9.39}], 'summary': 'Path length is m-1+n-1, followed by sublimation and tabulation for a tabulated solution using parameters i and j.', 'duration': 28.05, 'max_score': 770.371, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ770371.jpg'}, {'end': 927.255, 'src': 'embed', 'start': 897.6, 'weight': 4, 'content': [{'end': 900.381, 'text': 'Make sure you add this guy if and if j is greater than 0.', 'start': 897.6, 'duration': 2.781}, {'end': 901.822, 'text': 'Otherwise, it will just be these guys.', 'start': 900.381, 'duration': 1.441}, {'end': 905.345, 'text': 'So everyone, everyone of you knows this now.', 'start': 902.363, 'duration': 2.982}, {'end': 906.81, 'text': 'Perfect, perfect.', 'start': 906.189, 'duration': 0.621}, {'end': 910.195, 'text': "So, that's how we can easily do this stuff.", 'start': 906.93, 'duration': 3.265}, {'end': 914.862, 'text': 'Now, since we have done it in the tabulated form, how do you do space optimization?', 'start': 910.836, 'duration': 4.026}, {'end': 918.367, 'text': "I think I've taught you in the previous lecture how to do space optimization.", 'start': 914.882, 'duration': 3.485}, {'end': 919.448, 'text': 'Very, very simple.', 'start': 918.607, 'duration': 0.841}, {'end': 920.29, 'text': 'You know.', 'start': 919.969, 'duration': 0.321}, {'end': 922.732, 'text': 'you are at the 0th row.', 'start': 921.451, 'duration': 1.281}, {'end': 924.353, 'text': 'first i is 0.', 'start': 922.732, 'duration': 1.621}, {'end': 927.255, 'text': 'when you compute the first row, then i goes to 1.', 'start': 924.353, 'duration': 2.902}], 'summary': 'Discusses space optimization and condition for adding guy based on j > 0', 'duration': 29.655, 'max_score': 897.6, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ897600.jpg'}, {'end': 985.441, 'src': 'embed', 'start': 950.7, 'weight': 2, 'content': [{'end': 953.343, 'text': 'So just carry the previous row and the current row.', 'start': 950.7, 'duration': 2.643}, {'end': 958.309, 'text': "I've already taught you this in the lecture 8 of the grids.", 'start': 953.744, 'duration': 4.565}, {'end': 960.531, 'text': "How do you do this? I've already taught you this.", 'start': 958.809, 'duration': 1.722}, {'end': 962.153, 'text': "I'm not teaching you over here.", 'start': 960.591, 'duration': 1.562}, {'end': 963.574, 'text': 'I was just teaching you.', 'start': 962.653, 'duration': 0.921}, {'end': 968.848, 'text': 'how the recurrence will change if the question is slightly tweaked.', 'start': 964.625, 'duration': 4.223}, {'end': 972.191, 'text': "so i'm not explaining in depth because it's an extension.", 'start': 968.848, 'duration': 3.343}, {'end': 973.812, 'text': "it's an extension of the playlist.", 'start': 972.191, 'duration': 1.621}, {'end': 976.574, 'text': "so i'm assuming you've watched the lecture eight completely.", 'start': 973.812, 'duration': 2.762}, {'end': 985.441, 'text': "on that sole basis i'm just going on writing the recurrence relationships because it's more or less the extension of those problems, minor changes.", 'start': 976.574, 'duration': 8.867}], 'summary': 'Teaching about recurrence relationships, an extension of lecture 8 on grids.', 'duration': 34.741, 'max_score': 950.7, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ950700.jpg'}], 'start': 748.746, 'title': 'Dynamic programming in grids', 'summary': "Explains the recurrence relationships for dynamic programming in grids, with a time complexity of n cross m, space complexity of n cross m, and recursion stack space of m minus 1 plus n minus 1. it assumes prior knowledge from lecture 8 and provides initial conditions for the calculation of the answer as f(n-1, m-1) using the grid's size and elements.", 'chapters': [{'end': 919.448, 'start': 748.746, 'title': 'Dynamic programming: tabulation and space optimization', 'summary': 'Explains the process of converting a memoization solution into a tabulated solution for dynamic programming, with the time complexity being n cross m, space complexity n cross m, and recursion stack space of the path length m minus 1 plus n minus 1.', 'duration': 170.702, 'highlights': ['The time complexity of converting to a tabulated solution is n cross m, with a space complexity of n cross m and a recursion stack space of m minus 1 plus n minus 1.', 'The next step after memoization is to convert the solution into a tabulated form using parameters i and j ranging from 0 to n minus 1 and 0 to m minus 1, respectively.', 'The process of converting the memoization solution to a tabulated solution is straightforward, involving the use of parameters i and j, and the dp array of size n and m.', 'The lecture explains the process of solving dynamic programming on grids, with the final answer being dp of n minus 1, m minus 1, and the calculations involving minimal of up, left, and the previous values of i and j.', 'The lecture also covers the process of space optimization, with a reminder of the basic conditions for i and j, and the addition of specific conditions based on the values of i and j.']}, {'end': 1057.036, 'start': 919.969, 'title': 'Dynamic programming in grids', 'summary': "Explains the recurrence relationships for dynamic programming in grids, assuming prior knowledge from lecture 8, and provides initial conditions for the calculation of the answer as f(n-1, m-1) using the grid's size and elements.", 'duration': 137.067, 'highlights': ["The recurrence relationships for dynamic programming in grids are explained, assuming prior knowledge from lecture 8, and the initial condition for the answer is provided as f(n-1, m-1) using the grid's size and elements.", 'The lecture assumes that the viewers have watched lecture 8 completely before proceeding further with the explanation.', 'The approach is an extension of the problems discussed earlier, involving minor changes in the recurrence relationships for dynamic programming in grids.']}], 'duration': 308.29, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ748746.jpg', 'highlights': ['The time complexity of converting to a tabulated solution is n cross m', 'The process of converting the memoization solution to a tabulated solution is straightforward', 'The lecture explains the process of solving dynamic programming on grids', 'The recurrence relationships for dynamic programming in grids are explained', 'The lecture also covers the process of space optimization']}, {'end': 1416.934, 'segs': [{'end': 1090.152, 'src': 'embed', 'start': 1057.036, 'weight': 0, 'content': [{'end': 1064.58, 'text': 'i can and what i can return is the minimal of left comma up done.', 'start': 1057.036, 'duration': 7.544}, {'end': 1070.904, 'text': "so if i just quickly run this up, you'll see everything is running, but i'll not submit it because we need to memorize it.", 'start': 1064.58, 'duration': 6.324}, {'end': 1078.087, 'text': 'otherwise we know we will get something as a early.', 'start': 1070.904, 'duration': 7.183}, {'end': 1079.307, 'text': 'so how do you minimize again?', 'start': 1078.087, 'duration': 1.22}, {'end': 1081.368, 'text': 'very simple, this is how you minimize.', 'start': 1079.307, 'duration': 2.061}, {'end': 1083.629, 'text': 'declare the dp, pass the dp.', 'start': 1081.368, 'duration': 2.261}, {'end': 1090.152, 'text': 'just copy paste, and this time this will be dp.', 'start': 1083.629, 'duration': 6.523}], 'summary': 'The speaker emphasizes minimizing and declaring the dp, and suggests copying and pasting for efficiency.', 'duration': 33.116, 'max_score': 1057.036, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ1057036.jpg'}, {'end': 1156.484, 'src': 'embed', 'start': 1121.065, 'weight': 2, 'content': [{'end': 1123.747, 'text': 'Okay, so the recursion and memiation does work.', 'start': 1121.065, 'duration': 2.682}, {'end': 1127.99, 'text': 'What about the tabulation? Again, we know the tabulation is quite similar.', 'start': 1124.068, 'duration': 3.922}, {'end': 1135.995, 'text': "So, we'll be like db of n, vector of int, m comma minus, instead of minus 1, you can put a 0.", 'start': 1128.471, 'duration': 7.524}, {'end': 1136.835, 'text': 'Now, what are the states?', 'start': 1135.995, 'duration': 0.84}, {'end': 1140.877, 'text': 'We know the states are very simple i and i equal to 0, i less than n.', 'start': 1137.055, 'duration': 3.822}, {'end': 1141.817, 'text': 'i plus plus, correct?', 'start': 1140.877, 'duration': 0.94}, {'end': 1143.498, 'text': 'Over here, what are the states?', 'start': 1142.638, 'duration': 0.86}, {'end': 1146.579, 'text': 'i and ij equal to 0, j less than m.', 'start': 1143.518, 'duration': 3.061}, {'end': 1147.22, 'text': 'j plus plus.', 'start': 1146.579, 'duration': 0.641}, {'end': 1156.484, 'text': 'What is the next? If i is equal to equal to 0, j is equal to equal to 0, I can say dp of ij is equal to grade of ij, perfect.', 'start': 1148, 'duration': 8.484}], 'summary': 'Recursion, memiation, and tabulation implemented for dp of ij calculation.', 'duration': 35.419, 'max_score': 1121.065, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ1121065.jpg'}, {'end': 1214.592, 'src': 'heatmap', 'start': 1183.527, 'weight': 0.715, 'content': [{'end': 1187.17, 'text': 'but if i is not greater than zero, you remember, there is a base case.', 'start': 1183.527, 'duration': 3.643}, {'end': 1194.437, 'text': "if it's not greater than zero, then you return something maximum so that this path is neglected, so that this path is neglected.", 'start': 1187.17, 'duration': 7.267}, {'end': 1195.698, 'text': 'similarly, can you do for the left?', 'start': 1194.437, 'duration': 1.261}, {'end': 1196.845, 'text': 'Yes, we can.', 'start': 1196.345, 'duration': 0.5}, {'end': 1207.77, 'text': 'If the j is greater than 0, we say left path will be taking dp of i of the previous guy, the left guy, or else the left will be taking no path.', 'start': 1197.445, 'duration': 10.325}, {'end': 1208.65, 'text': "That's it.", 'start': 1208.35, 'duration': 0.3}, {'end': 1209.17, 'text': 'Simple as that.', 'start': 1208.69, 'duration': 0.48}, {'end': 1214.592, 'text': 'So, in this way, I can easily find out the left as well as the up.', 'start': 1209.57, 'duration': 5.022}], 'summary': 'Algorithm determines paths based on conditions, finding left and up paths.', 'duration': 31.065, 'max_score': 1183.527, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ1183527.jpg'}, {'end': 1242.071, 'src': 'heatmap', 'start': 1215.133, 'weight': 1, 'content': [{'end': 1223.636, 'text': 'So once I have figured out the left as well as the up, I know dp of i j will be minimum of the left or the up path right?', 'start': 1215.133, 'duration': 8.503}, {'end': 1229.36, 'text': "And once I've done this, I know the answer will be at dp of n minus 1 and m minus 1..", 'start': 1223.956, 'duration': 5.404}, {'end': 1234.124, 'text': "So, once I've done this, I can definitely return this, right? Yeah, it works fine.", 'start': 1229.36, 'duration': 4.764}, {'end': 1235.846, 'text': "Let's submit this code super quick.", 'start': 1234.505, 'duration': 1.341}, {'end': 1237.787, 'text': 'Runs fine.', 'start': 1237.247, 'duration': 0.54}, {'end': 1239.148, 'text': 'So, next step.', 'start': 1238.428, 'duration': 0.72}, {'end': 1242.071, 'text': 'Space optimization, which no one does.', 'start': 1240.51, 'duration': 1.561}], 'summary': 'Using dynamic programming, the minimum path sum is found, resulting in a successful code submission.', 'duration': 26.938, 'max_score': 1215.133, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ1215133.jpg'}, {'end': 1393.568, 'src': 'heatmap', 'start': 1341.707, 'weight': 3, 'content': [{'end': 1342.607, 'text': 'Previous will be current now.', 'start': 1341.707, 'duration': 0.9}, {'end': 1352.231, 'text': "And at the end of the day, n minus 1 means whenever this for loop ends, whenever this for loop ends, i's value will end up at n.", 'start': 1343.387, 'duration': 8.844}, {'end': 1355.033, 'text': 'This for loop will end when i is equal to n.', 'start': 1352.231, 'duration': 2.802}, {'end': 1359.815, 'text': 'So, for i equal to n, who will be the previous? n minus 1.', 'start': 1355.033, 'duration': 4.782}, {'end': 1360.395, 'text': 'So, just write n.', 'start': 1359.815, 'duration': 0.58}, {'end': 1365.401, 'text': 'and if i just submit this, it will be running.', 'start': 1362.439, 'duration': 2.962}, {'end': 1367.183, 'text': 'space optimization is very easy.', 'start': 1365.401, 'duration': 1.782}, {'end': 1368.083, 'text': 'see correct answer.', 'start': 1367.183, 'duration': 0.9}, {'end': 1370.105, 'text': 'submit it will be accepted.', 'start': 1368.083, 'duration': 2.022}, {'end': 1374.268, 'text': 'check this out, accept it as simple as it can get.', 'start': 1370.105, 'duration': 4.163}, {'end': 1378.295, 'text': "so it's not tough to space optimize, There's only a trick.", 'start': 1374.268, 'duration': 4.027}, {'end': 1382.198, 'text': "Whenever you see i-1 or something like that, you try to space optimize and it's very simple.", 'start': 1378.315, 'duration': 3.883}, {'end': 1386.662, 'text': 'Store the previous row, use it, store it again, use it, store it again, use it, store it again, use it.', 'start': 1382.598, 'duration': 4.064}, {'end': 1393.568, 'text': "That's how you will beat away, right? So yeah, I hope I was able to make you understand the third problem on the grits.", 'start': 1387.042, 'duration': 6.526}], 'summary': 'Optimize space by storing and reusing previous values to beat the third problem on the grits.', 'duration': 51.861, 'max_score': 1341.707, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ1341707.jpg'}], 'start': 1057.036, 'title': 'Dynamic programming', 'summary': 'Discusses minimization and tabulation, explaining dynamic programming through examples of finding the minimum path in a grid and space optimization methods, showcasing clear steps and emphasizing simplicity.', 'chapters': [{'end': 1143.498, 'start': 1057.036, 'title': 'Dynamic programming: minimization and tabulation', 'summary': 'Discusses the process of minimizing and tabulating dynamic programming, demonstrating the steps to declare and pass the dp, initializing stored answers, and implementing recursion and memoization before moving on to tabulation.', 'duration': 86.462, 'highlights': ['The process of minimizing dynamic programming involves declaring and passing the dp, initializing stored answers, and implementing recursion and memoization.', 'The chapter also covers the tabulation process for dynamic programming, highlighting the steps of declaring the dp and defining the states for tabulation.']}, {'end': 1416.934, 'start': 1143.518, 'title': 'Dynamic programming explanation', 'summary': 'Explains dynamic programming by breaking down the process of finding the minimum path in a grid, demonstrating a space optimization method, and emphasizing the simplicity of space optimization with clear steps.', 'duration': 273.416, 'highlights': ['The chapter explains the process of finding the minimum path in a grid using dynamic programming, highlighting the steps of determining the minimum path and the final result at dp of n minus 1 and m minus 1.', 'The speaker then simplifies the space optimization method by demonstrating the use of storing the previous row and utilizing it in the computation, emphasizing the ease of space optimization when dealing with i-1 or similar operations.', 'The speaker encourages engagement, requesting likes, comments, and subscriptions for the channel, maintaining a friendly and interactive approach with the audience.']}], 'duration': 359.898, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/_rgTlyky1uQ/pics/_rgTlyky1uQ1057036.jpg', 'highlights': ['The process of minimizing dynamic programming involves declaring and passing the dp, initializing stored answers, and implementing recursion and memoization.', 'The chapter explains the process of finding the minimum path in a grid using dynamic programming, highlighting the steps of determining the minimum path and the final result at dp of n minus 1 and m minus 1.', 'The chapter also covers the tabulation process for dynamic programming, highlighting the steps of declaring the dp and defining the states for tabulation.', 'The speaker then simplifies the space optimization method by demonstrating the use of storing the previous row and utilizing it in the computation, emphasizing the ease of space optimization when dealing with i-1 or similar operations.']}], 'highlights': ['The process involves finding minimal cost paths in a grid by moving upwards and leftwards, addressing overlapping subproblems, and optimizing the recursive function using memoization.', 'The importance of exploring all paths in finding the minimal cost path is emphasized, with recursion being the algorithm that tries out all possible paths.', 'The chapter explains the process of finding the minimum path in a grid using dynamic programming, highlighting the steps of determining the minimum path and the final result at dp of n minus 1 and m minus 1.', 'The time complexity of converting to a tabulated solution is n cross m', 'The process of minimizing dynamic programming involves declaring and passing the dp, initializing stored answers, and implementing recursion and memoization.', 'The lecture explains the process of solving dynamic programming on grids', 'The recurrence relationships for dynamic programming in grids are explained', 'The lecture also covers the process of space optimization', 'Following a greedy path in a non-uniform grid can lead to suboptimal solutions due to significant cost rise.', 'The problem discussed is the third problem from DP on grids, focusing on minimum path sum.']}