= Solution
A <divide-and-conquer algorithm> splits an instance into smaller instances of the same kind, solves them recursively, and combines their answers. The smaller instances should be sufficiently smaller to ensure <algorithm termination>; the combination cost determines whether splitting saves work. The two halves of <merge sort> illustrate this separation.
<Dynamic programming> identifies a collection of subproblems and dependencies among them, solves each distinct subproblem once, and stores its answer. A table in dependency order or <memoization> prevents repeated evaluation of overlapping subproblems. For optimization, an <optimal substructure> argument justifies constructing an optimal answer from optimal smaller answers.
A <greedy algorithm> repeatedly makes a locally best feasible choice and commits to it. It avoids exploring alternative continuations. <Algorithm correctness> therefore needs a <greedy-choice property>, often proved by replacing the first choice of an optimal solution with the greedy choice without worsening it.
$$
\boxed{\text{divide and combine; reuse subproblem answers; commit to safe local choices}.}
$$
Back to article page
