Fibonacci(斐波那契數)，大家多少一定會在教課書看過，老實說到我出社會工作都還沒搞懂，之前每次看到都覺得這是在幹嘛XD，直到後來我要去解一些DP(動態規劃)的題目，才回來重學XD。

那什麼是Fibonacci?

它是一個數列，來看這一串數字
0,1,1,2,3,5,8,13,21,34,55,89.....
每一個數字都是前面兩個的加總 ex: 1+1=2,1+2=3,2+3=5
轉化成公式

(from wiki)

leetcode有一題Fibonacci，順便解一下～

Leetcode #509. Fibonacci Number

Input一個數字n，回傳Fibonacci數列第n個位置的數值
ex.
n = 0, output: 0
n = 6, output: 8

程式:

func fib(n int) int {
	if n < 2 {
		return n
	}

	dp := map[int]int{}
	dp[0] = 0
	dp[1] = 1

	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}

	return dp[n]
}

明天來解一條DP的經典題～