DP (Dynamic Programming)

1. When to Use DP

When it comes to solving an algorithm problem, especially in a high-pressure scenario such as an interview, half the battle is figuring out how to even approach the problem. In the first section, we defined what makes a problem a good candidate for dynamic programming. Recall:

1. The problem can be broken down into "overlapping subproblems" - smaller versions of the original problem that are re-used multiple times
2. The problem has an "optimal substructure" - an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem

 

2. DP Characteristic

• What is the minimum cost of doing...
• What is the maximum profit from...
• How many ways are there to do...
• What is the longest possible...
• Is it possible to reach a certain point...
• When future "decisions" depend on earlier decisions.

 

3. DP vs. Memoization