Dynamic Programming
Dynamic Programming solves the problem by breaking down into smaller sub-problems, and storing the solution to each sub-problem so that each sub-problem is only solved once.
Dynamic Programming
It is one of the most commonly asked approach of problem solving during coding interview.
Dynamic Programming problems can be categorised into two types: Optimisation problems and Combinatorial problems.
- How to Identify if it is a DP problem or not : Build recursive solution and Identify the base cases. If smaller problems are called multiple times during recursion then the given problem can be solved by using dynamic programming.
- Decide if you want to implement it using Top down or bottom up approach : We recommend to compare the properties of both the approaches and undestand pros and cons of each. Usually most programmers prefer bottom up approach (Why? Think)
- Things to care during the bottom up approach : Size of the table, Table Initialisation, Iterative structure to fill the table and point in the table where your final solution get stored.
- Key ideas to learn : Understanding concepts, Doing practice and finding implementation patterns among problems
Concepts and Problems - Dynamic Programming
| # | Title | Difficulty | Companies |
|---|---|---|---|
1. | Idea of DP : Recursion and time memory tradeoff | ||
2. | Optimal Substructure and Overlapping subproblems Property | ||
3. | Memoization : Top Down Implementation | ||
4. | Tabulation : Bottom Up Implementation | ||
5. | What is Optimization and Combinatorial problems? | ||
6. | Comparison : Divide & Conquer vs Dynamic Programming | ||
7. | Example 1 : Finding nth fibonacci number | EASY | Amazon |
8. | Example 2 : Count of different ways to express N | EASY | |
9. | Example 3 : Longest Common Subsequence | MEDIUM | Amazon Google |
10. | Example 4 : Rod Cutting | MEDIUM | Google |
11. | Example 5 : Longest Palindromic Subsequence | HARD | Amazon LinkedIn PayPal |