subproblem

A smaller instance of the same problem, whose answer helps build the answer to the whole.

In more detail

Divide and conquer creates independent subproblems; dynamic programming exploits subproblems that repeat. Naming the subproblem precisely, such as "best value using the first i items within capacity w", is the key design step in both.

Related terms

Taught in

References