D&C works well when: Subproblems are independent: Unlike DP where subproblems overlap.
Combining is efficient: If combining is , D&C may not help.
Problem structure is recursive: Naturally splits into similar subproblems.
D&C vs DP:
- D&C: Subproblems don't overlap. Solve each once.
- DP: Subproblems overlap. Memoize to avoid recomputation.
D&C vs Greedy:
- D&C: Consider all subproblems.
- Greedy: Make one choice, never backtrack.
Red flags for D&C: If the combination step dominates (e.g., must consider all pairs), D&C may not reduce complexity.