Coder's Cat

## LeetCode: Fibonacci Number

2020-12-19

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 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:

## Recursive Solution

`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!

Join my Email List for more insights, It's Free!😋