Divide & Conquer vs Greedy vs Dynamic Programming

Feature	Divide & Conquer	Greedy	Dynamic Programming
Idea	Split into independent subproblems, solve recursively, combine.	Make locally optimal choice now, never undo, hope global optimum.	Split into overlapping subproblems, solve each once, store, combine via recurrence for global optimum.
Subproblems	Disjoint, independent.	Single decision path.	Overlapping, optimal substructure + overlapping.
Proof	Correctness by recursion + combine.	Needs greedy-choice + optimal substructure (exchange argument).	Needs optimal substructure + overlapping (table correctness).
Complexity	Recurrence $T(n)=aT(n/b)+f(n)$; e.g., Merge $O(n\log n)$.	Often $O(n\log n)$ or $O(n)$.	Table size × cost; often $O(n^2)$–$O(n^3)$ or $O(nW)$.
Examples	Merge Sort, Quick Sort, Binary Search, Strassen, Closest Pair.	Dijkstra (non-neg), Prim/Kruskal, Huffman, Fractional Knapsack, Activity Selection.	0/1 Knapsack, Matrix Chain, LCS, Edit Distance, Floyd-Warshall, Optimal BST.
When fails	Overlapping would cause exponential recomputation (Fibonacci $O(2^n)$ if pure D&C).	Fails where local ≠ global: 0/1 Knapsack, Coin change with arbitrary denominations (e.g., coins 1,3,4 for 6).	Overkill where greedy suffices (fractional knapsack DP $O(nW)$ vs greedy $O(n\log n)$).

Example Contrast — Knapsack $W=7$:

• Items (p/w): (10/2), (5/2), (8/3). D&C brute tries all $2^n$.
• Greedy ratio picks 10/2 first (5.0) → optimal for fractional but for 0/1 picks 10+8=18 weight5 vs DP optimum 10+8=18 (here same), but with weights 6,5,5 example greedy fails.
• DP enumerates table and gets exact 0/1 optimum.

Rule of thumb: Need overlapping? → DP. Need independent? → D&C. Local choice provably safe? → Greedy (fastest).