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.
Articles by others on the same topic
There are currently no matching articles.