Dynamic Programming is hard. But there are some ways that let us approach the problem more smoothly.
1. Identify if the problem needs Dynamic Programming
It is very important to find out whether the problem needs Dynamic Programming or not. Following cases normally requires Dynamic Programming.
- When you need to try every single case to find the result.
- When you need to find the possible smallest, biggest, longest, or shortest ... etc case (optimization problems).
Following list is from Neetcode's 5 Dynamic Programming Patterns Link:
1. Fibonacci
- When you need previous results to calculate the current result.
- Normally can be solved by updating two values recursively.
2. Zero/one knapsack
- Visualizing the problem as a n-ary tree can be helpful.
- Two possible cases: whether we take it or not. = Therefore, we do not need to consider some other cases.
3. Unbounded knapsack
- Visualizing the problem as a grid(like a chessboard) can help be helpful.
- Hash map is used.
- Need to consider every case to come up with the last answer.
4. Longest Common Subsequence
5. Palindromes
2. Figure out the subproblems
This is the most important step of the Dynamic Programming. Finding the subproblems and proving recursively solving those subproblems will lead to the answer are very hard. To shape the subproblems, we need to read the problem very thoroughly.
It is good to start from finding how many possible choices that each recursive step has. (e.g. The robot can go either left or bottom. There are only two options for each step.)Also, visualizing the solution as tree graph can help this step.
If there are too many options for each step, (e.g. Queen can move to any grid that is diagonal or adjacent. There are so many possibilities) we need to consider memoization.
3. Practice memoization
Most of the Dynamic Programming questions require to use memoization since the computation tend to have exponential time complexity. It is good to learn how to use 2D arrays, maps or sets.
Top comments (0)