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

Taught in

References