Summary
Keywords
Full Transcript
Dynamic programming is used to deal with problems that can be divided into similar sub-problems so that their results can be re-used. We aim to solve Knapsack Problems and other important coding problems. Learn more about Scaler: https://bit.ly/3gitdEx 🔹Introduction to Dynamic Programming: Dynamic Programming is most commonly an optimization over plain recursion. A recursive solution that has repeated calls for the same inputs is optimized using Dynamic Programming. In a nutshell, the results of subproblems are stored, to omit the need of re-computing them when required. This simple optimization reduces time complexities from exponential to polynomial. 🔹Applications of Dynamic Programming: Dynamic programming is used where we have problems, which can be divided into similar sub-problems so that their results can be re-used. From this exclusive dynamic programming tutorial, you can learn how to solve important coding problems. The following topics are covered in this video 👇🏼 0:00 - Introduction to Knapsack Problems 40:12 - Fractional Knapsack 1:05:13 - Longest Increasing Sub-sequence Problem 1:17:14 - Regular Expression Match Problem 1:47:16 - Max Sum Path in Binary Tree Problem 2:08:33 - Best Time to Buy and Sell Stocks Problem 2:27:57 - Min Jumps Array Problem 2:37:06 - Edit Distance Problem 2:59:05 - Rod Cutting problem 3:21:27 - Turn on the Bulbs Problem 3:44:00 - Valid Parenthesis Problem ---------------------------------------- About Scaler -------------------------------------------------- We are a tech-focused upskilling and reskilling platform catering to tech enthusiasts in universities and working professionals. There are more Scaler graduates working at Amazon than all of the IITs combined! Know More about Scaler: https://bit.ly/3gitdEx 📌 Follow us on Social and be a part of an amazing tech community📌 👉 Meet like-minded coder folks on Discord - https://discord.com/invite/ejFeksEtTq 👉 Tweets you cannot afford to miss out on - https://twitter.com/scaler_official 👉 Check out student success stories, expert opinions, and live classes on Linkedin - https://www.linkedin.com/school/scalerofficial 👉 Explore relatable memes and get access to exclusive updates on Instagram - https://www.instagram.com/scaler_official/ 📢 Be a part of our one of a kind telegram community: https://t.me/Scalercommunity 🔔 Hit that bell icon to get notified of all our new videos 🔔 If you liked this video, please don't forget to like and comment. Never miss out on our exclusive videos to help boost your coding career! Subscribe to Scaler now! https://www.youtube.com/Scaler?sub_confirmation=1 #dynamicprogramming #dsalgo #knapsack
Continue this lesson in the app
Install CourseHive on Android or iOS to keep learning while you move.
