Skip to content

Latest commit

 

History

History
20 lines (11 loc) · 952 Bytes

dq.md

File metadata and controls

20 lines (11 loc) · 952 Bytes

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.

  1. Divide the problem into a number of subproblems that are smaller instances of the same problem.

  2. Conquer subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.

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