You are using an outdated browser. Please update your browser for a better user experience.

Fibonacci

dynamic

The fibonacci sequence is defined by F(n) = F(n-1) + F(n-2), where F(1) = 1 and F(0) = 0. The naive solution (recursive) is quite obvious, but has a runtime of O(2^n) which is bad. Is there a way that you can calculate the sequence in a shorter time?