Is this a correct way to phrase the difference between the three?
- DP, Greedy, and Divide and Conquer is only appliciable to problems with optimal substructure. I.e. they can be solved by finding optimal solutions of subproblems.
- All three of these algorithms merely describe how to navigate the "subproblem space".
- Greedy arrives at solution by continuously picking the locally optimal choice.
- Dynamic programming is used when greedy doesn't provide optimal solution, but the subproblems that need to be solved overlap. As a result, we can cache answers to the overlapping subproblems and greatly reduce subproblems that need to be solved.
- Divide and conquer is used when subproblems don't overlap, but the problem still has optimal substructure
- Brute force is used when problem doesn't have optimal substructure.