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 or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblem.
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.
Famous quotes containing the word overlapping:
“The absolute things, the last things, the overlapping things, are the truly philosophic concerns; all superior minds feel seriously about them, and the mind with the shortest views is simply the mind of the more shallow man.”
—William James (1842–1910)