Course Overview
Get an overview of what this course is about.
Dynamic programming patterns and why we need them
Coding interviews are hard. You never know what questions you’ll be asked, or which strategy to use to crack the hardest questions. To make matters worse, the interviewer expects you to eventually (if not immediately) converge to an optimal solution.
Dynamic programming (DP) is an advanced optimization technique applied to recursive solutions. However, DP is not a one-size-fits-all technique and there is a long list of problems that can be solved using dynamic programming.
To highlight the subtle differences between problems that affect the design of optimized solutions, we have organized problems into five major patterns, each centered on one prototypical problem. A pattern is a code blueprint that can be customized to optimally solve many related problems.
Mastering these patterns gives you the tools to find the optimized approach to solve new problems, freeing you from the need to commit individual solutions to memory. The two key things you need to know are:
How does each pattern work?
How to decide which pattern to apply to a given problem?
About this course
This course presents the most popular dynamic programming interview questions, organized as a set of 5 patterns. Conventional wisdom recommends going through all these difficult coding questions to prepare for a technical interview. However, without an adequate conceptual foundation, this approach is essentially just cramming for an exam. The purpose of classifying problems into patterns is to help you build up a robust conceptual framework. This will help you to think critically about any new problem and tackle it with the most appropriate techniques.
Each lesson drills down to focus on the core of a programming problem to present both the logic and the implementation of its recommended solution. We have included interactive elements, such as "Try it yourself" and illustrated walkthroughs, to help build your understanding of the problem and the dynamic programming solutions.
Course structure
Each of the 5 patterns in the diagram below has been used to solve at least 5 problems each, allowing you to understand the core of the technique and experiment with its application to related problems.
The first problem in each chapter is typically the foundational problem of that pattern. Once you have fully understood the problem structure, and worked through the progression from the naive recursive solution all the way to the bottom-up tabulation approach of this first prototypical problem, you will be in a good position to analyze the other problems within the pattern and develop a sound conceptual model of how these problems relate to each other.
Strengths of this course
The course offers a detailed introduction to the dynamic problem-solving techniques in each pattern, including a visual representation of how the pattern works, basic guidelines for using the pattern, and some real-world applications. These introductions equip you with the necessary skills to identify the distinguishing features of a new problem that can help you correctly identify the underlying pattern.
After presenting the problem in a clear and unambiguous manner, we explain how to solve it using a naive recursive approach. We then discuss the limitations of the naive approach and also identify the opportunities available for optimization. Building on this understanding, we present the first dynamic programming solution where we add memoization logic to the naive recursive solution. This allows you to see the problem clearly as being composed of overlapping subproblems and define their inter-relationships. This helps to design the second dynamic programming solution using the bottom-up approach, also known as tabulation.
Visual representations of solutions allow you to dive deep into the algorithm and track how variables and data structures are modified by the program logic. The coded solution features sufficiently detailed in-line comments to help you understand the implementation of the design. Finally, the time and space complexities of the solutions are stated, which provides you a useful indication of how each solution performs in the worst case. This helps you to develop the skills to effectively compare the three solutions to the same problem, and to keep time and space complexity measures in mind when writing your own code.