|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/top-50-dynamic-programming-java-algorithms-coding-questions/
课程评论：没有评论
本课程“Java算法50题（程序员面试和竞赛编程系列）”旨在帮助学员掌握动态规划（Dynamic Programming，简称DP）这一强大的算法优化技术。 课程首先会介绍动态规划的基本概念，包括它如何应用于纯递归问题，以及判断一个问题是否适合使用动态规划的两个关键属性：最优子结构（optimal substructure）和重叠子问题（overlapping subproblem）。课程会解释为何动态规划能够提高效率，即通过存储子问题的解来避免重复计算，并利用最优子结构优化决策过程。 课程的教学方法将侧重于实践，通过讲解和代码演示相结合的方式，深入剖析50个在编码面试和竞赛编程中最常出现的动态规划问题。针对每个问题，学员将学习如何： 1. 理解问题陈述和范例。 2. 识别递归解法。 3. 构建递归树，发现递归模式。 4. 确认最优子结构和重叠子问题。 5. 编写递归代码。 6. 将递归解法转化为自顶向下（Memoization）和自底向上（Tabulation）的动态规划实现。 7. 探索可能的优化解法（空间或时间）。 8. 分析不同解法的时间和空间复杂度。 课程内容将避免枯燥的PPT讲解，转而采用白板讲解和代码并行演示，鼓励学员在面试中清晰地表达解题思路，并能主动思考和提问。 课程将涵盖的50个动态规划问题包括（但不限于）：二项式系数、最大切分段数、朋友配对问题、钢管切割问题、金矿问题、Catalan数、最大连续子数组和（Kadane算法）、爬楼梯、最长递增子序列的和、房屋抢劫、子集和问题、最长公共子序列、最长递增子序列、带权作业调度、最长数对链、特定差值的最大不相交数对和、扔鸡蛋问题、数组最小移除使最大值与最小化差值等。 通过本课程的学习，学员将能系统地提升解决动态规划问题的能力，为应对技术面试和算法竞赛做好充分准备。
Welcome to this course!Here, you will go through a "journey" of the Top 50 Dynamic Programming Java Algorithm questions that are asked in coding interviews as well as competitive programming. So let's start by answering the most fundamental questions:What is Dynamic Programming Algorithm?Dynamic programming is a powerful optimization technique for plain recursion problems. If you can break down a problem into simpler sub-problems (optimal substructure) and these sub-problems are repetitive in nature, then you can convert this problem into a Dynamic Programming Solution.In this course, we will start with a basic introduction to Dynamic Programming. We will understand what Dynamic Programming is and how to find out whether a recursive problem can be solved using Dynamic Programming.Can Dynamic Programming solve all problems?Dynamic Programming cannot solve all problems. The dynamic programming algorithm is meant to solve only those problems that have optimal substructure and overlapping subproblem properties.Why is Dynamic Programming faster?Dynamic Programming is faster because we break down a problem into various smaller subproblems. Then, we store the solutions of these subproblems in a table or cache whenever we encounter them first. Hence, if we get the same subproblem later on, instead of recomputing it, we fetch it from the storage and return it. This saves us a lot of time.Moreover, since a Dynamic Programming algorithm required optimal substructure property. It means that the best solution to the initial subproblem can be constructed from the optimal solutions of its subproblems. Hence, we can easily eliminate the need to consider all the possible subproblem solutions. This reduces the time complexity of the algorithm.What will be our approach when you take this course?We will solve the 50 most popular Dynamic Programming examples asked in coding interviews. For each question, our approach will be: Understand the problem statement with a few examples.Check if it can be solved recursively.Build a recursion tree and determine the recursive pattern.Check for optimal substructure and overlapping subproblem properties using the recursive tree.Derive the recursive code for the solution.Using the recursive code, convert the problem to a Top-Down (Memoization) approach.Then solve the same problem with the Bottom-Up (Tabulation) approach.Come up with an optimized DP solution if possible (space or time).Discuss the time and space complexities of all the approaches.Don't worry, we won't bore you with slides and PPTs. We will understand each algorithm using a whiteboard explanation of approaches and the code in parallel. This will help you to be more expressive during your interviews.In any interview, the interviewer wants to know the thinking or the approach that you are going to take to solve a problem given by him. Thus, it becomes very necessary to keep reciting the approach out loud. The format of these videos will help you to think out loud and will promote discussions and you will be able to question back the interviewer.What are the top 50 Dynamic Programming Problems or Examples asked in Coding Interview and Competitive Programming that we will discuss?Lecture 1: IntroductionLecture 2: Introduction to Dynamic Programming - Recursive, Memoization, TabulationLecture 3: Binomial Coefficient ProblemLecture 4: Maximize the Cut SegmentsLecture 5: Friends Pairing ProblemLecture 6: Rod Cutting ProblemLecture 7: Gold Mine ProblemLecture 8: Nth Catalan NumberLecture 9: Largest Sum Contiguous SubArray (Kadane's Algorithm)Lecture 10: Climbing StairsLecture 11: Maximum Sum Increasing SubsequenceLecture 12: House RobberLecture 13: Subset Sum ProblemLecture 14: Longest Common SubsequenceLecture 15: Longest Increasing SubsequenceLecture 16: Weighted Job SchedulingLecture 17: Maximum Length Chain of PairsLecture 18: Maximum Sum of Disjoint Pairs with Specific DifferencesLecture 19: Egg-Dropping ProblemLecture 20: Minimum Removals from Array to make Max - Min
