Overlapping subproblems

In computer science, a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times.

For example, the problem of computing the [Fibonacci sequence] exhibits overlapping subproblems. The problem of computing the Nth Fibonacci number, F(n), can be broken down into the subproblems of computing F(n-1) and F(n-2), and then adding the two. The subproblem of computing F(n-1) can itself be broken down into a subproblem that involves computing F(n-2). Therefore the computation of F(n-2) is reused, and the Fibonacci sequence thus exhibits overlapping subproblems.