寫一個(gè)函數(shù)，輸入 n ，求斐波那契（Fibonacci）數(shù)列的第 n 項(xiàng)褂乍。斐波那契數(shù)列的定義如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數(shù)列由 0 和 1 開始帖渠，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出尤溜。
答案需要取模 1e9+7（1000000007）倔叼，如計(jì)算初始結(jié)果為：1000000008，請返回 1靴跛。
示例 1
輸入：n = 2
輸出：1
示例 2：
輸入：n = 5
輸出：5
代碼
/**
斐波那契數(shù)列:1,1,2,3,5,8,13,21,34.....時(shí)間復(fù)雜度O(n)
*/
public func fib(_ N: Int) -> Int {
var fibs: [Int : Int] = [0: 0, 1: 1, 2: 1]
return fib(N, fibs: &fibs)
}
func fib(_ N: Int, fibs: inout [Int: Int]) -> Int {
var result = 0
if let fib = fibs[N] {
return fib
}
result = fib(N - 1, fibs: &fibs) + fib(N - 2, fibs: &fibs)
if result >= 1000000007 {
result = result % 1000000007
}
fibs[N] = result
return result
}
