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
- divide and conquer — A problem-solving technique that splits a problem into independent smaller pieces, solves each recursively, and combines their answers.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- overlapping subproblems — The property that a recursive solution solves the same subproblems again and again.
- optimal substructure — The property that an optimal solution to a problem is built from optimal solutions to its subproblems.
Taught in
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers