題目描述
寫一個(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崖媚，請(qǐng)返回 1亦歉。
解題思路
簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問題
f[n] = f[n-1] + f[n]
f[0] = 0, f[1] = 1
class Solution {
public int fib(int n) {
if (n == 1 || n == 0) {
return n;
}
int[] f = new int[n + 1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
f[i] = f[i] % 1000000007;
}
return f[n];
}
}
