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).
Example 1:

Explanation
Fibonacci numbers is a wellknown 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:
Recursive Solution
Fibonacci numbers
is defined in recursive paradigm, it’s can be implemented easily in a oneline 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).
Topbottom Solution with Memoization
To remove the duplicated computation, we can add memoization for the recursive function.

Dynamic programming: Iterative Solution
If we use a bottomtop computation style, we could get this iterative solution.
