The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
Given n, calculate F(n).
Fibonacci numbers is a well-known mathematical concept, which we also call the Fibonacci sequence. The Fibonacci sequence is closely related to the golden ratio and this is a great video to explain it:
Fibonacci numbers is defined in recursive paradigm, it’s can be implemented easily in a one-line recursive function.
The computation process is:
But this algorithm is worst in time complexity:
Time complexity is O(2^N), space complexity is O(N).
Top-bottom Solution with Memoization
To remove the duplicated computation, we can add memoization for the recursive function.
Dynamic programming: Iterative Solution
If we use a bottom-top computation style, we could get this iterative solution.
Preparing for an interview? Check out this!