DP vs Greedy vs Divide and Conquer, is this correct?

Is this a correct way to phrase the difference between the three?

  1. 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.
  2. All three of these algorithms merely describe how to navigate the "subproblem space".
  3. Greedy arrives at solution by continuously picking the locally optimal choice.
  4. 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.
  5. Divide and conquer is used when subproblems don't overlap, but the problem still has optimal substructure
  6. Brute force is used when problem doesn't have optimal substructure.
Comments (1)