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.
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.