AI engineering glossary · Data structures algorithms
What is overlapping subproblems?
Overlapping subproblems: The property that a recursive solution solves the same smaller problems many times. Recognising it signals that caching results, as in dynamic programming, will pay off. Recognising this property is the first sign that dynamic programming may help.
Overlapping subproblems: an example
The recursive call tree for fib(5) computes fib(3) twice and fib(2) three times.
Related terms
More Data structures algorithms terms
Where you learn it
Overlapping subproblems is part of the AI Engineering Program, which teaches it with notes, a hands-on lab and an exam. The first lesson is free.