overlapping subproblems
The property that a recursive solution solves the same subproblems again and again.
In more detail
Naive Fibonacci computes fib(30) over a million times inside fib(40). Storing each answer the first time turns exponential work into linear work. If subproblems never repeat, as in merge sort, divide and conquer is enough and caching gains nothing.
Related terms
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- memoisation — Caching a function's results by its arguments so that repeated calls return the stored answer instead of recomputing it.
- optimal substructure — The property that an optimal solution to a problem is built from optimal solutions to its subproblems.
Taught in
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers