Overlapping subproblems

[1][2] [3] For example, the problem of computing the Fibonacci sequence exhibits overlapping subproblems.

Therefore, the computation of F(n − 2) is reused, and the Fibonacci sequence thus exhibits overlapping subproblems.

A naive recursive approach to such a problem generally fails due to an exponential complexity.

If the problem also shares an optimal substructure property, dynamic programming is a good way to work it out.

In contrast, the fibonacci_mem version exhibits a more linear increase in complexity.