题目链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
image.png
题目解析
这道题目采用动态规划的思路进行解答，题目中已经给出了公式和基础的起始值。
public int fib(int n) {
// F(N) = F(N-1) + F(N-2)
if (n <2){
return n;
}
final int MOD = 1000000007;
//fn2 对应F(n-2)
//fn1 对应F(n-1)
//fn 对应F(n)
int fn2 =0,fn1 = 0,fn = 1;
for (int i = 2;i<=n;i++){
fn2 = fn1;
fn1 = fn;
fn = (fn2 + fn1) % MOD;
}
return fn;
}
复杂度分析
空间复杂度: O(N)。
时间复杂度: O(1)。
网友评论