title
DP 1. Introduction to Dynamic Programming | Memoization | Tabulation | Space Optimization Techniques

description
Lecture Notes: https://takeuforward.org/data-structure/dynamic-programming-introduction/ 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 what is memoization, what is tabulation, what is space optimisation with the classic Fibonacci problem. You might feel that this question has been done by you, but I will still urge you to watch this till the end because this is going to teach you a bunch of stuff. 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 1. Introduction to Dynamic Programming | Memoization | Tabulation | Space Optimization Techniques', 'heatmap': [{'end': 1344.925, 'start': 1321.212, 'weight': 0.763}, {'end': 1484.295, 'start': 1399.63, 'weight': 0.786}], 'summary': 'Series introduces the ultimate dynamic programming playlist with 60 to 70 videos covering recursion, tabulation, and space optimization, aiming to provide optimal solutions. it emphasizes memoization, tabulation, and space complexity, focusing on english for universal understanding, and discusses optimizing fibonacci number computation with reduced redundant calculations, conversion of recursion to dynamic programming, and tabulation, as well as space and time complexity analysis.', 'chapters': [{'end': 140.46, 'segs': [{'end': 82.882, 'src': 'embed', 'start': 61.122, 'weight': 0, 'content': [{'end': 71.171, 'text': 'point number one why the reason is because this series will contain the maximum number of videos which none of the other channels have given.', 'start': 61.122, 'duration': 10.049}, {'end': 74.694, 'text': 'this series will be containing around 60 to 70 videos.', 'start': 71.171, 'duration': 3.523}, {'end': 77.036, 'text': 'yes, i repeat, 60 to 70 videos.', 'start': 74.694, 'duration': 2.342}, {'end': 82.161, 'text': 'so when you solve 60 to 70 videos on a given pattern, you tend to master a topic.', 'start': 77.036, 'duration': 5.125}, {'end': 82.882, 'text': 'yes, you do.', 'start': 82.161, 'duration': 0.721}], 'summary': 'This series will have 60-70 videos, offering maximum content for mastering topics.', 'duration': 21.76, 'max_score': 61.122, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY61122.jpg'}, {'end': 140.46, 'src': 'embed', 'start': 101.578, 'weight': 1, 'content': [{'end': 104.98, 'text': 'someone has also done the recursion way and then the tabulation way.', 'start': 101.578, 'duration': 3.402}, {'end': 106.522, 'text': "so what's different in yours?", 'start': 104.98, 'duration': 1.542}, {'end': 114.106, 'text': "the difference is i'm gonna do recursion, I'm going to do tabulation and after that I'm going to do space optimization,", 'start': 106.522, 'duration': 7.584}, {'end': 116.587, 'text': 'which none of the creators in the market have done.', 'start': 114.106, 'duration': 2.481}, {'end': 125.271, 'text': "For every problem I'll be telling you the most optimal solution which I guarantee no one has ever taught in even the paid courses.", 'start': 116.847, 'duration': 8.424}, {'end': 128.773, 'text': 'Yeah, I might not be able to give you teaching assistance.', 'start': 125.771, 'duration': 3.002}, {'end': 130.294, 'text': 'That is something which I will not promise.', 'start': 128.853, 'duration': 1.441}, {'end': 138.178, 'text': "But the content is going to be so crisp and so clear that you will learn completely and you'll have no doubts.", 'start': 130.674, 'duration': 7.504}, {'end': 140.46, 'text': "So without waiting, let's get started.", 'start': 138.538, 'duration': 1.922}], 'summary': 'Offering unique problem-solving methods with space optimization and clear, concise teaching.', 'duration': 38.882, 'max_score': 101.578, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY101578.jpg'}], 'start': 0.469, 'title': 'Ultimate dynamic programming series', 'summary': 'Introduces the ultimate dynamic programming playlist containing 60 to 70 videos, covering recursion, tabulation, and space optimization, promising to provide the most optimal solutions and ensuring mastery of the topic.', 'chapters': [{'end': 140.46, 'start': 0.469, 'title': 'Ultimate dynamic programming series', 'summary': 'Introduces the ultimate dynamic programming playlist containing 60 to 70 videos, covering recursion, tabulation, and space optimization, promising to provide the most optimal solutions and ensuring mastery of the topic.', 'duration': 139.991, 'highlights': ['The ultimate dynamic programming series will contain 60 to 70 videos, allowing for comprehensive mastery of the topic.', 'The series will cover recursion, tabulation, and space optimization, offering the most optimal solutions not taught in other courses.', 'The content promises to be crisp and clear, ensuring comprehensive learning and minimal doubts.']}], 'duration': 139.991, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY469.jpg', 'highlights': ['The ultimate dynamic programming series will contain 60 to 70 videos, allowing for comprehensive mastery of the topic.', 'The series will cover recursion, tabulation, and space optimization, offering the most optimal solutions not taught in other courses.', 'The content promises to be crisp and clear, ensuring comprehensive learning and minimal doubts.']}, {'end': 780.152, 'segs': [{'end': 245.56, 'src': 'embed', 'start': 141.74, 'weight': 0, 'content': [{'end': 147.123, 'text': 'What is DP? Those who cannot remember the past are condemned to repeat it.', 'start': 141.74, 'duration': 5.383}, {'end': 152.567, 'text': 'This is one of the famous quotes for DP, which is dynamic programming.', 'start': 147.584, 'duration': 4.983}, {'end': 160.187, 'text': 'Yes Now when I talk about dynamic programming, there are a couple of ways in which people tend to solve it.', 'start': 152.727, 'duration': 7.46}, {'end': 167.559, 'text': 'One is the tabulation way while the other one is the memoization way.', 'start': 160.868, 'duration': 6.691}, {'end': 170.612, 'text': 'lot of people call to tend to call.', 'start': 168.649, 'duration': 1.963}, {'end': 173.335, 'text': "this memorization doesn't matter.", 'start': 170.612, 'duration': 2.723}, {'end': 175.458, 'text': "as long as you understand, it's okay.", 'start': 173.335, 'duration': 2.123}, {'end': 181.726, 'text': "another thing the series is going to be entirely in english, so it doesn't matter where you're, where you are located,", 'start': 175.458, 'duration': 6.268}, {'end': 185.09, 'text': "you're going to understand each and every word of this series.", 'start': 181.726, 'duration': 3.364}, {'end': 191.333, 'text': 'So when I say tabulation, it means a bottom up, dynamic programming.', 'start': 185.931, 'duration': 5.402}, {'end': 199.176, 'text': "Yes Now when I say bottom up, it doesn't necessarily mean that you're going to start from zero till end.", 'start': 191.553, 'duration': 7.623}, {'end': 200.836, 'text': 'It can be vice versa also.', 'start': 199.476, 'duration': 1.36}, {'end': 204.797, 'text': "But as the name suggests, it's a bottom up dynamic programming.", 'start': 201.036, 'duration': 3.761}, {'end': 210.68, 'text': "And when I say memorization, it's a top down, dynamic programming.", 'start': 205.178, 'duration': 5.502}, {'end': 215.382, 'text': "again. when i say top down, it doesn't mean that it is going to be from n to zero.", 'start': 210.68, 'duration': 4.702}, {'end': 215.762, 'text': 'it can be.', 'start': 215.382, 'duration': 0.38}, {'end': 219.803, 'text': 'the vice versa also depends on your implementation skills.', 'start': 215.762, 'duration': 4.041}, {'end': 227.907, 'text': 'so, going forward in every lecture, what i am going to do is i am going to teach you, uh, the memorization topic.', 'start': 219.803, 'duration': 8.104}, {'end': 231.748, 'text': "then i'm going to discuss the time complexity and the space complexity.", 'start': 227.907, 'duration': 3.841}, {'end': 235.49, 'text': "once i've done that, i will move to the tabulation.", 'start': 231.748, 'duration': 3.742}, {'end': 243.879, 'text': "yes, i'll move to the tabulation and i'll teach you again the time complexity and the space complexity that the tabulation takes.", 'start': 236.556, 'duration': 7.323}, {'end': 245.56, 'text': 'what after tabulation?', 'start': 243.879, 'duration': 1.681}], 'summary': 'The lecture covers dynamic programming with a focus on tabulation and memoization, emphasizing understanding and universal accessibility.', 'duration': 103.82, 'max_score': 141.74, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY141740.jpg'}, {'end': 368.736, 'src': 'embed', 'start': 345.25, 'weight': 2, 'content': [{'end': 353.736, 'text': 'i will still recommend you to do the first 10 videos where the lecture number sixth and the lecture number seventh are of highest importance.', 'start': 345.25, 'duration': 8.486}, {'end': 359.14, 'text': 'please, please do the lecture number six and the lecture number seven, for sure.', 'start': 353.736, 'duration': 5.404}, {'end': 362.203, 'text': 'so the first problem fibonacci number.', 'start': 359.14, 'duration': 3.063}, {'end': 368.736, 'text': "what's a Fibonacci number?", 'start': 366.994, 'duration': 1.742}], 'summary': 'First 10 videos recommended, lectures 6 and 7 most important. topic: fibonacci number.', 'duration': 23.486, 'max_score': 345.25, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY345250.jpg'}, {'end': 419.056, 'src': 'embed', 'start': 390.376, 'weight': 5, 'content': [{'end': 396.659, 'text': 'similarly, if you take the next two fibonacci numbers and you add them up, you get the next fibonacci number, correct.', 'start': 390.376, 'duration': 6.283}, {'end': 400.3, 'text': 'so what i can say is the recurrence relation.', 'start': 396.659, 'duration': 3.641}, {'end': 405.962, 'text': "again, i have already explained this, so i'll not be explaining the recursion relations in depth in any of the lectures.", 'start': 400.3, 'duration': 5.662}, {'end': 408.423, 'text': "i'm assuming you are very, very good at recursion.", 'start': 405.962, 'duration': 2.461}, {'end': 419.056, 'text': 'so the recursion relation comes up to be f of n minus 1, plus f of n minus 2, without any doubt, because whenever i say five, it says that okay,', 'start': 408.423, 'duration': 10.633}], 'summary': 'Recurrence relation in fibonacci sequence: f(n-1) + f(n-2)', 'duration': 28.68, 'max_score': 390.376, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY390376.jpg'}, {'end': 737.825, 'src': 'embed', 'start': 706.454, 'weight': 3, 'content': [{'end': 714.796, 'text': 'we solved a problem f of 2 over here, and we again encounter that same problem over here.', 'start': 706.454, 'duration': 8.342}, {'end': 719.837, 'text': "so that's what we call as over lapping sub problems.", 'start': 714.796, 'duration': 5.041}, {'end': 733.142, 'text': "remember this term Whenever we end up solving same sub-problems again, again, again, that's when we call it overlapping sub-problems.", 'start': 719.837, 'duration': 13.305}, {'end': 737.825, 'text': "Make sense? So, it's a sub-problem which has been solved.", 'start': 733.302, 'duration': 4.523}], 'summary': 'The concept of overlapping sub-problems occurs when the same sub-problems are solved repeatedly.', 'duration': 31.371, 'max_score': 706.454, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY706454.jpg'}], 'start': 141.74, 'title': 'Dynamic programming', 'summary': 'Explains dynamic programming, focusing on tabulation and memoization methods, emphasizing time and space complexity, and recommending completion of the recursion playlist, all in english for universal understanding.', 'chapters': [{'end': 219.803, 'start': 141.74, 'title': 'Understanding dynamic programming: tabulation vs. memoization', 'summary': 'Explains the concept of dynamic programming, specifically focusing on the tabulation and memoization methods of solving it, and emphasizes the series being entirely in english for universal understanding.', 'duration': 78.063, 'highlights': ['The series is going to be entirely in English, ensuring universal understanding.', 'Dynamic programming can be solved using tabulation or memoization methods.', 'Tabulation in dynamic programming refers to a bottom-up approach, while memoization refers to a top-down approach.']}, {'end': 780.152, 'start': 219.803, 'title': 'Dynamic programming: fibonacci and space optimization', 'summary': 'Covers the approach for teaching dynamic programming, emphasizing the memorization topic, time and space complexity, tabulation, and space optimization, with a recommendation to complete the recursion playlist.', 'duration': 560.349, 'highlights': ['The chapter emphasizes the approach for teaching dynamic programming, including memorization, time and space complexity, tabulation, and space optimization.', 'The lecturer recommends completing the recursion playlist, particularly emphasizing the importance of the sixth and seventh lectures.', 'The lecturer explains the concept of Fibonacci numbers and the recurrence relation f(n) = f(n-1) + f(n-2).', 'The lecturer discusses the approach of optimizing space and the significance of overlapping sub-problems in dynamic programming.']}], 'duration': 638.412, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY141740.jpg', 'highlights': ['Dynamic programming can be solved using tabulation or memoization methods.', 'The chapter emphasizes the approach for teaching dynamic programming, including memorization, time and space complexity, tabulation, and space optimization.', 'The lecturer recommends completing the recursion playlist, particularly emphasizing the importance of the sixth and seventh lectures.', 'The lecturer discusses the approach of optimizing space and the significance of overlapping sub-problems in dynamic programming.', 'Tabulation in dynamic programming refers to a bottom-up approach, while memoization refers to a top-down approach.', 'The lecturer explains the concept of Fibonacci numbers and the recurrence relation f(n) = f(n-1) + f(n-2).', 'The series is going to be entirely in English, ensuring universal understanding.']}, {'end': 1014.989, 'segs': [{'end': 856.528, 'src': 'embed', 'start': 802.36, 'weight': 0, 'content': [{'end': 804.102, 'text': "So, you'll return 1.", 'start': 802.36, 'duration': 1.742}, {'end': 807.848, 'text': 'So, f of 4 is 2 plus 1, 3.', 'start': 804.102, 'duration': 3.746}, {'end': 810.331, 'text': 'So, we can return f of 4 as 3.', 'start': 807.848, 'duration': 2.483}, {'end': 812.855, 'text': 'Now, over here we come to f of 3.', 'start': 810.331, 'duration': 2.524}, {'end': 816.039, 'text': 'Will you compute f of 3? No, Baba, no.', 'start': 812.855, 'duration': 3.184}, {'end': 821.404, 'text': 'Why? Because f of 3 has been pre-computed.', 'start': 816.32, 'duration': 5.084}, {'end': 827.529, 'text': 'This f of 3 is a sub-problem where we have been asked to find the third Fibonacci number.', 'start': 821.965, 'duration': 5.564}, {'end': 832.173, 'text': 'And we see that the third Fibonacci number has already been figured out.', 'start': 827.95, 'duration': 4.223}, {'end': 838.539, 'text': 'So, is there a point of going to f of 2, going to f of 1, going to f of 1, going to f of 0?', 'start': 832.454, 'duration': 6.085}, {'end': 839.579, 'text': 'Is there a necessity?', 'start': 838.539, 'duration': 1.04}, {'end': 842.542, 'text': 'There is no necessity, because this has already been computed.', 'start': 840, 'duration': 2.542}, {'end': 844.563, 'text': 'This sub-problem has already been solved.', 'start': 842.842, 'duration': 1.721}, {'end': 845.684, 'text': 'So, what we do is.', 'start': 844.924, 'duration': 0.76}, {'end': 849.766, 'text': "we go across and see what's the value stored.", 'start': 846.645, 'duration': 3.121}, {'end': 853.607, 'text': "two, so let's return it, so we'll return that value.", 'start': 849.766, 'duration': 3.841}, {'end': 855.328, 'text': 'so, over here we get three.', 'start': 853.607, 'duration': 1.721}, {'end': 856.528, 'text': 'over here we get two.', 'start': 855.328, 'duration': 1.2}], 'summary': 'The algorithm computes and returns values for fibonacci numbers, avoiding unnecessary recomputation.', 'duration': 54.168, 'max_score': 802.36, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY802360.jpg'}, {'end': 921.651, 'src': 'embed', 'start': 890.334, 'weight': 1, 'content': [{'end': 891.735, 'text': 'So, if you carefully see.', 'start': 890.334, 'duration': 1.401}, {'end': 901.618, 'text': 'Where are the subproblems? What are the subproblems? There is a subproblem as f of 5, there is a problem as f of 4, f of 3, f of 2, f of 1, f of 0.', 'start': 892.813, 'duration': 8.805}, {'end': 907.962, 'text': 'So, can I say at max, the subproblems are from 0 to 5? Okay, makes sense, 0 to 5.', 'start': 901.618, 'duration': 6.344}, {'end': 921.651, 'text': 'So can I say if I can create an array of 6 size, if I can create an array of 6 size and I can call that as some dp array.', 'start': 907.962, 'duration': 13.689}], 'summary': 'Identifying 6 subproblems from 0 to 5, suggests creating an array of 6 size for dynamic programming.', 'duration': 31.317, 'max_score': 890.334, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY890334.jpg'}], 'start': 780.152, 'title': 'Fibonacci number computation and dynamic programming', 'summary': 'Discusses the computation of fibonacci numbers using memoization to avoid redundant recalculations and emphasizes the concept of dynamic programming, resulting in significant time savings and reduced redundant calculations.', 'chapters': [{'end': 890.334, 'start': 780.152, 'title': 'Fibonacci number computation', 'summary': 'Discusses the computation of fibonacci numbers using memoization, with an emphasis on avoiding redundant recalculations and reusing precomputed values, ultimately leading to optimized computation of the fibonacci sequence.', 'duration': 110.182, 'highlights': ['Using memoization to avoid redundant recalculations and reuse precomputed values leads to optimized computation of the Fibonacci sequence.', 'Explaining the avoidance of recomputing f of 2 due to its precomputed value of 1, resulting in a return value of 1.', 'Illustrating the avoidance of computing f of 3 by utilizing the precomputed value, thus eliminating the need to traverse sub-problems f of 2, f of 1, and f of 0.', 'Demonstrating the addition of precomputed values for f of 2 and f of 3 to compute f of 5, showcasing the optimization achieved through memoization.']}, {'end': 1014.989, 'start': 890.334, 'title': 'Dynamic programming explained', 'summary': 'Explains the concept of dynamic programming using the example of computing fibonacci numbers, where subproblems are solved and stored in a dynamic programming array to optimize the computation, resulting in significant time savings and reduced redundant calculations.', 'duration': 124.655, 'highlights': ['Subproblems are solved and stored in a dynamic programming array to optimize computation, resulting in significant time savings and reduced redundant calculations.', 'The approach involves creating an array of size 6 to store the computed values of subproblems, allowing for efficient retrieval and reuse of previously solved subproblems.', 'The value of subproblems is stored in the array, allowing for easy retrieval and reuse of previously computed values, leading to optimized computation and reduced redundancy.']}], 'duration': 234.837, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY780152.jpg', 'highlights': ['Using memoization to avoid redundant recalculations and reuse precomputed values leads to optimized computation of the Fibonacci sequence.', 'Subproblems are solved and stored in a dynamic programming array to optimize computation, resulting in significant time savings and reduced redundant calculations.', 'The approach involves creating an array of size 6 to store the computed values of subproblems, allowing for efficient retrieval and reuse of previously solved subproblems.', 'Illustrating the avoidance of computing f of 3 by utilizing the precomputed value, thus eliminating the need to traverse sub-problems f of 2, f of 1, and f of 0.']}, {'end': 1416.531, 'segs': [{'end': 1145.774, 'src': 'embed', 'start': 1116.203, 'weight': 3, 'content': [{'end': 1117.604, 'text': "I'll store it in DP of 1.", 'start': 1116.203, 'duration': 1.401}, {'end': 1118.324, 'text': "That's just step 1.", 'start': 1117.604, 'duration': 0.72}, {'end': 1121.146, 'text': 'To convert a recursion to memorization.', 'start': 1118.324, 'duration': 2.822}, {'end': 1123.628, 'text': "What's the step 2? The step 2 is.", 'start': 1121.606, 'duration': 2.022}, {'end': 1126.409, 'text': 'There is a call made to F of 1.', 'start': 1124.248, 'duration': 2.161}, {'end': 1127.31, 'text': 'F of n.', 'start': 1126.409, 'duration': 0.901}, {'end': 1129.471, 'text': 'There is a call made to F of n.', 'start': 1127.31, 'duration': 2.161}, {'end': 1130.652, 'text': 'You can check base cases.', 'start': 1129.471, 'duration': 1.181}, {'end': 1132.453, 'text': 'After the base cases.', 'start': 1131.412, 'duration': 1.041}, {'end': 1134.349, 'text': 'You are calling.', 'start': 1133.288, 'duration': 1.061}, {'end': 1136.35, 'text': 'Again sub problems.', 'start': 1135.389, 'duration': 0.961}, {'end': 1138.251, 'text': 'You are calling sub problems over here.', 'start': 1136.73, 'duration': 1.521}, {'end': 1139.891, 'text': 'Like you are calling sub problems.', 'start': 1138.271, 'duration': 1.62}, {'end': 1141.052, 'text': 'To go and solve them.', 'start': 1140.072, 'duration': 0.98}, {'end': 1142.613, 'text': 'But over here.', 'start': 1141.772, 'duration': 0.841}, {'end': 1144.214, 'text': 'You will not call sub problems.', 'start': 1142.653, 'duration': 1.561}, {'end': 1145.774, 'text': 'You will first check.', 'start': 1144.914, 'duration': 0.86}], 'summary': 'The process involves converting recursion to memorization, with step 1 being storing in dp of 1 and step 2 involving making a call to f of 1.', 'duration': 29.571, 'max_score': 1116.203, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1116203.jpg'}, {'end': 1223.265, 'src': 'embed', 'start': 1169.901, 'weight': 0, 'content': [{'end': 1185.375, 'text': 'so in order to convert a recursion To a dynamic programming, I implemented kind of three steps where I can say the step 0 is declaring an array.', 'start': 1169.901, 'duration': 15.474}, {'end': 1187.737, 'text': 'considering the size of the subproblems.', 'start': 1185.375, 'duration': 2.362}, {'end': 1190.579, 'text': 'like over here, there were n subproblems.', 'start': 1187.737, 'duration': 2.842}, {'end': 1193.441, 'text': 'thereby I declared an array of size n.', 'start': 1190.579, 'duration': 2.862}, {'end': 1198.425, 'text': 'Step 1, storing the answer which is being computed for every subproblem.', 'start': 1193.441, 'duration': 4.984}, {'end': 1205.311, 'text': 'Step 2, checking if the sub problem has been previously solved.', 'start': 1198.945, 'duration': 6.366}, {'end': 1209.234, 'text': 'if it is previously solved, then the value will not be minus one.', 'start': 1205.311, 'duration': 3.923}, {'end': 1210.875, 'text': 'thereby i can easily return it.', 'start': 1209.234, 'duration': 1.641}, {'end': 1217.521, 'text': 'so if you follow these three steps, you can convert any recursion to a dynamic programming solution.', 'start': 1210.875, 'duration': 6.646}, {'end': 1223.265, 'text': 'so the gist of the dynamic programming lies in be in mastering recursion.', 'start': 1217.521, 'duration': 5.744}], 'summary': 'To convert recursion to dynamic programming: declare array, store answers, check previous solutions. dp essence is mastering recursion.', 'duration': 53.364, 'max_score': 1169.901, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1169901.jpg'}, {'end': 1321.992, 'src': 'embed', 'start': 1291.89, 'weight': 2, 'content': [{'end': 1294.112, 'text': "So, generally, I'll recommend you to use vectors.", 'start': 1291.89, 'duration': 2.222}, {'end': 1295.133, 'text': "That's how I do it.", 'start': 1294.192, 'duration': 0.941}, {'end': 1296.894, 'text': 'You can use arrays as well.', 'start': 1295.773, 'duration': 1.121}, {'end': 1299.256, 'text': 'dp n of minus 1.', 'start': 1296.994, 'duration': 2.262}, {'end': 1303.839, 'text': 'And what you can do is you can say c out of f of n and you can pass on this dp parameter.', 'start': 1299.256, 'duration': 4.583}, {'end': 1306.802, 'text': 'And over here, you can always take the vector by reference.', 'start': 1304.24, 'duration': 2.562}, {'end': 1314.227, 'text': 'Okay By reference, you can take it so that this will be changed on every step.', 'start': 1307.682, 'duration': 6.545}, {'end': 1315.808, 'text': 'So, you can just do it like this.', 'start': 1314.747, 'duration': 1.061}, {'end': 1318.17, 'text': "And over here, if I give 5, you'll see 5 coming out.", 'start': 1315.908, 'duration': 2.262}, {'end': 1319.231, 'text': 'I can just run it.', 'start': 1318.65, 'duration': 0.581}, {'end': 1321.992, 'text': 'Sorry, N plus one.', 'start': 1321.212, 'duration': 0.78}], 'summary': 'Recommend using vectors for dynamic programming with a vector of size n+1.', 'duration': 30.102, 'max_score': 1291.89, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1291890.jpg'}, {'end': 1371.136, 'src': 'heatmap', 'start': 1321.212, 'weight': 4, 'content': [{'end': 1321.992, 'text': 'Sorry, N plus one.', 'start': 1321.212, 'duration': 0.78}, {'end': 1323.153, 'text': "I'll do it N plus one.", 'start': 1322.173, 'duration': 0.98}, {'end': 1327.536, 'text': "So over here, if I just run it, you'll see the Fibonacci number will come out to be five.", 'start': 1323.753, 'duration': 3.783}, {'end': 1334.039, 'text': 'So step, one step, two step, declaration, three steps.', 'start': 1327.976, 'duration': 6.063}, {'end': 1341.944, 'text': 'So in this way, you can avoid using global variables and you can easily write your Fibonacci or any of the DPs.', 'start': 1334.64, 'duration': 7.304}, {'end': 1344.925, 'text': "So that's how you do the first step, which is recursion.", 'start': 1342.324, 'duration': 2.601}, {'end': 1347.347, 'text': "So I've taught you the first step, which is recursion.", 'start': 1345.286, 'duration': 2.061}, {'end': 1352.308, 'text': 'memoization I have to teach you the time complexity and the space complexity.', 'start': 1348.433, 'duration': 3.875}, {'end': 1354.415, 'text': "Let's analyze that as well.", 'start': 1353.131, 'duration': 1.284}, {'end': 1360.287, 'text': 'So, over here, f of 5 called f of 4.', 'start': 1356.004, 'duration': 4.283}, {'end': 1362.089, 'text': 'f of 4 called f of 3.', 'start': 1360.287, 'duration': 1.802}, {'end': 1363.81, 'text': 'f of 3 called f of 2 and then 1.', 'start': 1362.089, 'duration': 1.721}, {'end': 1366.813, 'text': '5 steps or n steps.', 'start': 1363.81, 'duration': 3.003}, {'end': 1371.136, 'text': 'Are these calls going into deep? Are these calls going into deep? No.', 'start': 1367.413, 'duration': 3.723}], 'summary': 'Teaching recursion and memoization with fibonacci example, avoiding global variables. analyzing time and space complexity.', 'duration': 49.924, 'max_score': 1321.212, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1321212.jpg'}, {'end': 1422.193, 'src': 'embed', 'start': 1393.248, 'weight': 1, 'content': [{'end': 1399.31, 'text': 'Yes Thereby, I can say the time complexity to be V go of n, which is a linear pattern.', 'start': 1393.248, 'duration': 6.062}, {'end': 1405.211, 'text': 'What about the space complexity? I can say I am using a recursion stack space, which is V go of n.', 'start': 1399.63, 'duration': 5.581}, {'end': 1411.641, 'text': "So I'm using a recursion stack space because if you've seen my recursion lectures, you'll understand what a stack space is.", 'start': 1405.791, 'duration': 5.85}, {'end': 1414.645, 'text': "And I'm using a big O of n for array.", 'start': 1412.221, 'duration': 2.424}, {'end': 1416.531, 'text': "That's what I'm using.", 'start': 1415.831, 'duration': 0.7}, {'end': 1422.193, 'text': 'So we have covered up memorization with time complexity as well as space complexity.', 'start': 1416.991, 'duration': 5.202}], 'summary': 'Time complexity: o(n), space complexity: o(n). covered memorization.', 'duration': 28.945, 'max_score': 1393.248, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1393248.jpg'}], 'start': 1014.989, 'title': 'Converting recursion to dynamic programming and implementing fibonacci', 'summary': 'Explains converting recursion to dynamic programming, including steps such as declaring a dp array, storing computed values, and checking if subproblems have been previously solved. it also discusses implementing fibonacci using recursion and memoization, analyzing time complexity as linear and space complexity as n.', 'chapters': [{'end': 1244.236, 'start': 1014.989, 'title': 'Recursion to dynamic programming', 'summary': 'Explains the process of converting recursion to dynamic programming, involving steps such as declaring a dp array, storing computed values, and checking if subproblems have been previously solved, allowing for the conversion of any recursion to a dynamic programming solution.', 'duration': 229.247, 'highlights': ['Step 0 involves declaring an array considering the size of the subproblems, like in the given example, where an array of size n was declared for n subproblems.', 'Step 1 includes storing the answer computed for every subproblem in the DP array, facilitating the conversion of a recursion to memorization.', 'Step 2 entails checking if the subproblem has been previously solved, enabling the return of the stored value if it is not equal to minus one, thus converting the recursion to dynamic programming.']}, {'end': 1416.531, 'start': 1244.236, 'title': 'Fibonacci recursion and memoization', 'summary': 'Discusses the implementation of fibonacci using recursion and memoization, suggesting the use of vectors to avoid global variables and providing analysis of time complexity as linear and space complexity as n.', 'duration': 172.295, 'highlights': ['The time complexity of the Fibonacci recursion implementation is O(n), where n represents the input size, and the space complexity is O(n) as well due to the recursion stack space and the array.', 'The chapter recommends using vectors instead of arrays to avoid using global variables and easily write Fibonacci or any other dynamic programming algorithms.', "The implementation involves the declaration of an integer n, using a recursive function 'f' to calculate the Fibonacci number, and employing memoization to avoid redundant computations.", 'The analysis of the recursion calls reveals a linear pattern, with constant calls and a time complexity of O(n), as the deeper calls do not go into deep recursion, demonstrating a linear pattern.']}], 'duration': 401.542, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1014989.jpg', 'highlights': ['Step 0 involves declaring an array considering the size of the subproblems, like in the given example, where an array of size n was declared for n subproblems.', 'The time complexity of the Fibonacci recursion implementation is O(n), where n represents the input size, and the space complexity is O(n) as well due to the recursion stack space and the array.', 'The chapter recommends using vectors instead of arrays to avoid using global variables and easily write Fibonacci or any other dynamic programming algorithms.', 'Step 1 includes storing the answer computed for every subproblem in the DP array, facilitating the conversion of a recursion to memorization.', "The implementation involves the declaration of an integer n, using a recursive function 'f' to calculate the Fibonacci number, and employing memoization to avoid redundant computations.", 'Step 2 entails checking if the subproblem has been previously solved, enabling the return of the stored value if it is not equal to minus one, thus converting the recursion to dynamic programming.', 'The analysis of the recursion calls reveals a linear pattern, with constant calls and a time complexity of O(n), as the deeper calls do not go into deep recursion, demonstrating a linear pattern.']}, {'end': 1617.396, 'segs': [{'end': 1445.946, 'src': 'embed', 'start': 1416.991, 'weight': 0, 'content': [{'end': 1422.193, 'text': 'So we have covered up memorization with time complexity as well as space complexity.', 'start': 1416.991, 'duration': 5.202}, {'end': 1429.475, 'text': "Now the question arises, how do you convert a recursive solution into a tabulation format? Okay, that's very, very important.", 'start': 1422.313, 'duration': 7.162}, {'end': 1439.337, 'text': 'How do you convert a recursion into a tabulation? So remember, as a tabulation, what did the name suggest? Bottom up, okay.', 'start': 1429.855, 'duration': 9.482}, {'end': 1445.946, 'text': 'So try to go from the base case, the required answer.', 'start': 1439.737, 'duration': 6.209}], 'summary': 'Covers time and space complexity, converting recursion to tabulation', 'duration': 28.955, 'max_score': 1416.991, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1416991.jpg'}, {'end': 1539.096, 'src': 'embed', 'start': 1490.111, 'weight': 3, 'content': [{'end': 1497.634, 'text': 'Can I say there are a couple of base cases if I carefully see which states n lesser than equal to 1 given that we require 0th and 1th Fibonacci.', 'start': 1490.111, 'duration': 7.523}, {'end': 1507.439, 'text': 'Can I say dp of like the 0th Fibonacci is 0 and can I say dp of 1 is 1 because that is what the base case exactly states.', 'start': 1498.235, 'duration': 9.204}, {'end': 1514.622, 'text': 'So, you are going to write the exact same thing dp of 0 equal to 0 and dp of 1 equal to 1 because that is what the base case is.', 'start': 1507.459, 'duration': 7.163}, {'end': 1524.028, 'text': 'So, in order to convert this into tabulation, you will write this dp of 0 equal to 0, 1 equal to 1 written.', 'start': 1515.242, 'duration': 8.786}, {'end': 1525.29, 'text': "what's the next step?", 'start': 1524.028, 'duration': 1.262}, {'end': 1528.374, 'text': 'the next step is going to be very, very simple.', 'start': 1525.29, 'duration': 3.084}, {'end': 1532.999, 'text': 'you again go back and look out the look at the recursion relationship.', 'start': 1528.374, 'duration': 4.625}, {'end': 1539.096, 'text': 'so the recursion relationship is this f of n minus 1 plus f of n minus 2.', 'start': 1532.999, 'duration': 6.097}], 'summary': 'Defining base cases for fibonacci series, converting to tabulation, and establishing recursion relationship.', 'duration': 48.985, 'max_score': 1490.111, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1490111.jpg'}, {'end': 1617.396, 'src': 'embed', 'start': 1568.675, 'weight': 1, 'content': [{'end': 1571.198, 'text': 'so from 2 to n is what you write.', 'start': 1568.675, 'duration': 2.523}, {'end': 1576.684, 'text': "okay, and you're going to write dp of i, because that is what you wrote over there.", 'start': 1571.198, 'duration': 5.486}, {'end': 1586.495, 'text': "in recursion equal to, instead of f of n, minus 1, you'll write dp of i, minus 1, plus dp of i, minus 2, similar stuff you'll write.", 'start': 1576.684, 'duration': 9.811}, {'end': 1591.46, 'text': 'just you change it to i and similar stuff.', 'start': 1587.478, 'duration': 3.982}, {'end': 1595.521, 'text': "and this is how you can make a tabulation interesting, isn't it?", 'start': 1591.46, 'duration': 4.061}, {'end': 1601.164, 'text': 'just look at the recurrence and try to convert that into a tabulation, and it becomes easy.', 'start': 1595.521, 'duration': 5.643}, {'end': 1604.647, 'text': "the time complexity over here it's.", 'start': 1602.205, 'duration': 2.442}, {'end': 1607.088, 'text': 'we go of n again.', 'start': 1604.647, 'duration': 2.441}, {'end': 1607.609, 'text': "what's the space?", 'start': 1607.088, 'duration': 0.521}, {'end': 1612.853, 'text': 'complexity this time is just a big, often no recursion stack space.', 'start': 1607.609, 'duration': 5.244}, {'end': 1617.396, 'text': "so it's a better solution that, uh, than the recursion or the memory i should want,", 'start': 1612.853, 'duration': 4.543}], 'summary': 'Tabulation provides better space complexity than recursion for dynamic programming.', 'duration': 48.721, 'max_score': 1568.675, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1568675.jpg'}], 'start': 1416.991, 'title': 'Converting recursive solutions to tabulation', 'summary': 'Covers converting recursive solutions to tabulation, emphasizing bottom-up approach as a significant technique in dynamic programming. it also explains tabulation in recursion, discussing base cases, conversion steps, and time and space complexity, offering a better solution than recursion.', 'chapters': [{'end': 1471.813, 'start': 1416.991, 'title': 'Tabulation conversion: recursive to bottom-up', 'summary': 'Covers the process of converting a recursive solution into tabulation format, emphasizing the bottom-up approach as a significant technique in dynamic programming.', 'duration': 54.822, 'highlights': ['The process of converting a recursive solution into tabulation format is the key focus, highlighting the importance of the bottom-up approach in dynamic programming.', "Tabulation involves a bottom-up approach, starting from the base case and progressing to the required answer, in contrast to recursion's top-down progression."]}, {'end': 1617.396, 'start': 1472.233, 'title': 'Tabulation in recursion', 'summary': 'Explains the process of converting a recursion relationship into tabulation, discussing base cases, conversion steps, and time and space complexity, presenting a better solution than recursion.', 'duration': 145.163, 'highlights': ['The first step in converting a recursion relationship into tabulation is to initialize the DP array with the same values used in recursion, such as initializing the DP array of n plus one in Fibonacci.', 'Identifying and writing the base cases for the tabulation, such as setting dp of 0 equal to 0 and dp of 1 equal to 1 for the 0th and 1st Fibonacci numbers, is crucial in the conversion process.', 'Converting the recursion relationship, f of n minus 1 plus f of n minus 2, into tabulation by changing the variables to dp and writing the transition from 2 to n, helps in creating an efficient tabulation.', 'The time complexity of the tabulation solution is O(n), while the space complexity is just a big O(n) without recursion stack space, making it a better solution than recursion.']}], 'duration': 200.405, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1416991.jpg', 'highlights': ["Tabulation involves a bottom-up approach, starting from the base case and progressing to the required answer, in contrast to recursion's top-down progression.", 'The time complexity of the tabulation solution is O(n), while the space complexity is just a big O(n) without recursion stack space, making it a better solution than recursion.', 'Converting the recursion relationship, f of n minus 1 plus f of n minus 2, into tabulation by changing the variables to dp and writing the transition from 2 to n, helps in creating an efficient tabulation.', 'Identifying and writing the base cases for the tabulation, such as setting dp of 0 equal to 0 and dp of 1 equal to 1 for the 0th and 1st Fibonacci numbers, is crucial in the conversion process.', 'The process of converting a recursive solution into tabulation format is the key focus, highlighting the importance of the bottom-up approach in dynamic programming.', 'The first step in converting a recursion relationship into tabulation is to initialize the DP array with the same values used in recursion, such as initializing the DP array of n plus one in Fibonacci.']}, {'end': 2021.95, 'segs': [{'end': 1851.76, 'src': 'embed', 'start': 1823.49, 'weight': 0, 'content': [{'end': 1827.291, 'text': 'So you will have the previous stored as the Fibonacci number.', 'start': 1823.49, 'duration': 3.801}, {'end': 1830.412, 'text': 'So in this way, you can optimize the space as well.', 'start': 1827.731, 'duration': 2.681}, {'end': 1832.833, 'text': 'I have eliminated the space used.', 'start': 1830.872, 'duration': 1.961}, {'end': 1835.534, 'text': "I've used just a couple of variables.", 'start': 1833.713, 'duration': 1.821}, {'end': 1843.096, 'text': 'So if I just use my sublime text now, what I can do is I can say, okay, previous two is zero.', 'start': 1836.014, 'duration': 7.082}, {'end': 1846.218, 'text': 'Previous 1 is 1.', 'start': 1844.838, 'duration': 1.38}, {'end': 1851.76, 'text': 'I can go on saying i equal to 2, i less than equal to n, i plus plus.', 'start': 1846.218, 'duration': 5.542}], 'summary': 'Optimized fibonacci calculation reduces space usage with just two variables.', 'duration': 28.27, 'max_score': 1823.49, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1823490.jpg'}, {'end': 1913.596, 'src': 'embed', 'start': 1889.623, 'weight': 1, 'content': [{'end': 1895.807, 'text': "So as simple as it can get, what I've done, I've eliminated the extra space that I was using.", 'start': 1889.623, 'duration': 6.184}, {'end': 1901.65, 'text': 'Now this boils down into a time complexity of bigger of n and the space complexity of bigger of 1.', 'start': 1896.387, 'duration': 5.263}, {'end': 1909.295, 'text': 'So going forward in every problem, we will be observing this pattern where we will be actually using the previous guys and the second previous guys.', 'start': 1901.65, 'duration': 7.645}, {'end': 1911.395, 'text': 'Or something similar to that.', 'start': 1910.035, 'duration': 1.36}, {'end': 1913.596, 'text': "So we don't need to always create an array.", 'start': 1911.696, 'duration': 1.9}], 'summary': 'Reduced space complexity to o(1), time complexity to o(n)', 'duration': 23.973, 'max_score': 1889.623, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1889623.jpg'}, {'end': 1997.537, 'src': 'embed', 'start': 1970.384, 'weight': 2, 'content': [{'end': 1977.207, 'text': 'like from every from now onwards on every video, at least try to write this small word understood.', 'start': 1970.384, 'duration': 6.823}, {'end': 1980.849, 'text': 'that is what i will be expecting from you if you keep on doing this.', 'start': 1977.207, 'duration': 3.642}, {'end': 1985.391, 'text': 'i will be bringing videos every day till 60, like for two months.', 'start': 1980.849, 'duration': 4.542}, {'end': 1991.454, 'text': "i'll bring video every day, unless until i'm ill or i'm traveling, i'll make sure i'll bring the videos every day.", 'start': 1985.391, 'duration': 6.063}, {'end': 1997.537, 'text': 'but this is what i require from you uh, like and an understood comment on the uh video.', 'start': 1991.454, 'duration': 6.083}], 'summary': "Expecting 'understood' comment on every video, planning daily videos for 60 days.", 'duration': 27.153, 'max_score': 1970.384, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1970384.jpg'}], 'start': 1617.396, 'title': 'Fibonacci number optimization', 'summary': 'Demonstrates an intuitive solution to the fibonacci number problem, optimizing space complexity to o(1) and time complexity to o(n), leading to a significant reduction in space usage.', 'chapters': [{'end': 2021.95, 'start': 1617.396, 'title': 'Fibonacci number optimization', 'summary': 'Demonstrates an intuitive solution to the fibonacci number problem by optimizing space complexity to o(1) and time complexity to o(n), utilizing the previous and second previous elements instead of an array, leading to a significant reduction in space usage.', 'duration': 404.554, 'highlights': ['The chapter demonstrates an intuitive solution to the Fibonacci number problem by optimizing space complexity to O(1) and time complexity to O(n), utilizing the previous and second previous elements instead of an array, leading to a significant reduction in space usage.', 'The previous and second previous elements are used to calculate the current element, allowing for the elimination of extra space usage and demonstrating a time complexity of O(n) and space complexity of O(1).', "Encouragement for viewers to subscribe, like, and participate in a trend of leaving 'understood' comments, emphasizing a commitment to daily video uploads for two months."]}], 'duration': 404.554, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/tyB0ztf0DNY/pics/tyB0ztf0DNY1617396.jpg', 'highlights': ['Demonstrates an intuitive solution to the Fibonacci number problem by optimizing space complexity to O(1) and time complexity to O(n), utilizing the previous and second previous elements instead of an array, leading to a significant reduction in space usage.', 'The previous and second previous elements are used to calculate the current element, allowing for the elimination of extra space usage and demonstrating a time complexity of O(n) and space complexity of O(1).', "Encouragement for viewers to subscribe, like, and participate in a trend of leaving 'understood' comments, emphasizing a commitment to daily video uploads for two months."]}], 'highlights': ['The ultimate dynamic programming series will contain 60 to 70 videos, allowing for comprehensive mastery of the topic.', 'Using memoization to avoid redundant recalculations and reuse precomputed values leads to optimized computation of the Fibonacci sequence.', 'Demonstrates an intuitive solution to the Fibonacci number problem by optimizing space complexity to O(1) and time complexity to O(n), utilizing the previous and second previous elements instead of an array, leading to a significant reduction in space usage.', "Tabulation involves a bottom-up approach, starting from the base case and progressing to the required answer, in contrast to recursion's top-down progression.", 'Dynamic programming can be solved using tabulation or memoization methods.', 'The series will cover recursion, tabulation, and space optimization, offering the most optimal solutions not taught in other courses.', 'The content promises to be crisp and clear, ensuring comprehensive learning and minimal doubts.', 'The chapter emphasizes the approach for teaching dynamic programming, including memorization, time and space complexity, tabulation, and space optimization.', 'The lecturer recommends completing the recursion playlist, particularly emphasizing the importance of the sixth and seventh lectures.', 'The approach involves creating an array of size 6 to store the computed values of subproblems, allowing for efficient retrieval and reuse of previously solved subproblems.']}