> For the complete documentation index, see [llms.txt](https://hannahpun.gitbook.io/leetcode-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hannahpun.gitbook.io/leetcode-note/dynamic-programing/509-fibonacci-number.md).

# # 509 Fibonacci Number (有圖)

[LeetCode](https://leetcode.com/problems/fibonacci-number/)

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

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

寫出 Fibonacci sequence
```

```
Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    
};
```

### 解釋

![](/files/-LrAHjQJ2xm_8jBdF41Y)

```
F(0) : 0
F(1) : 1
F(2) : 1
F(6) : 8
```

每個數字都是前兩個的總和, 0 + 1 = 1, 1+1 = 2, 2+1 = 3 以此類推

* 第 0 項 F(0) = 0
* 第 1 項 F(1) = 1
* 第 n 項 F(n ) = f( n-1 ) + f( n-2 ) // 第 n-1 項 + 第 n-2 項

![](/files/-LrAHud8EIflK3VgKyW1)

![](/files/-LrAI-JjAtsb9_MwmUwA)

每一項都分成 f(n-1) + f(n-2) 一直拆到 f(1) = 1, f(0) =0 為止, 然後再把它全部加起來 (黃色數字) 就等於 5，而總共要執行 15 次這個函式

### Code

```
var fib = function(N) {
	if(num == 0){
		return 0;
	}else if(num == 1){
		return 1;
	}else{
		return F(num - 1) + F(num - 2)
	}
}
fib(5); // 5
```

### 改善

優化，把算過的儲存進 cache

```
let cacheSet = new Map();
 // basic
var fib = function(N) {
    if(cacheSet.has(N)){
        return cacheSet.get(N)
    }
    if(N==0){
        cacheSet.set(N, 0)
    }else if(N==1){
        cacheSet.set(N, 1)
    }else{
        cacheSet.set(N, fib(N - 1) + fib(N - 2))
    }
    return cacheSet.get(N)
};

```