Divide and Conquer
Overview
Break the problem into several subproblems that are similar to the original proble but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.
-
Divide the problem into a number of subproblems that are smaller instances of the same problem.
-
Conquer subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
-
Combine solutions to subproblems into the solution for the original problem.
Variations
When combined with a lookup table that stores the results of previously solved sub-problems to avoid solving them repeatedly, it can be referred to as dynamic programming or memoization.