题目

题解

这题与[lc]509一样，区别在于结果需要取余，而对于最终结果取余和对于每一位取余再计算下一个数字答案是一样的。具体分析见(https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/solution/mian-shi-ti-10-i-fei-bo-na-qi-shu-lie-dong-tai-gui/)的循环取余法。

1. 递归

写法很简单，时间复杂度很高，有大量重复运算无法通过OJ，就不写了

  • 时间复杂度$O(2^n)$
  • 空间复杂度$O(n)$

2. 递推公式

其实也可以用一个dp数组存每个位置的数，但是没必要，每个位置的数只与前两位有关，用两个变量存前两个数并实时更新。再注意一下0，1，2位的特殊情况就好
本题还要注意取模，且必须每次运算完取模，若最后取模会溢出

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$
class Solution {//两个方法。1.递推公式
public:
    int fib(int n) {
        if(n==0) return 0;//特殊情况
        int a=1, b=1;//设置前两位
        int c = 0;
        for(int i=2; i<n; ++i){
            c = (a + b)%(int)(1e9+7);
            a = b;
            b = c;
        }//递推
        return b;
    }
};

3. 通项公式

斐波那契数列的通项公式是 $$ F_n = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] $$
详细的推导见这里

  • 时间复杂度$O(log(n))$，n次方的pow 方法将会用去 $log(n)$ 的时间。
  • 空间复杂度$O(1)$ 详见[leetcode]509题题解，因为这道题需要取模，测试数据比较大，使用这个方法在最后结果取模总会出错。