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 n-th 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.
See also
 | This article has not been added to any content categories. Please help out by adding categories to it so that it can be listed with similar articles, in addition to a stub category. (September 2010) |
 | This computer science article is a stub. You can help Wikipedia by expanding it. |