Day.21 Fibonacci

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的经典题～