Kata

A problem with the common recursive solution when calculating the Fibonacci series is that it takes a long time to calculate the result even for quite small numbers of n. The reason being that the same values gets calculated over and over again, leading to an exponential increase of computations as n increases.

To remedy this one can use caching, or memoization, of previous calculations. And also entirely skip the recursion part.

Improve the given algorithm so that it can be used to calculate the Fibonacci sequence for 1 <= n <= 2000.

Some important things:

• The initial solution will time out if submitted, this is expected.
• Indexing starts from 1. DynamicFibonacci(0) must return -1.
• In this kata the Fibonacci series starts 1, 1, 2, 3, 5. No 0 is included.
• Max n is 2000. If n > 2000 the function must return -1.
• Very large numbers are expected. Beware of overflow.