题目

题解

这题和爬楼梯是一样的，这题与剑指offer10一样，三种方法

1. 递归

这个方法最慢，因为有大量的重复运算，写法最简单，就不写了

  • 时间复杂度$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);;
            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)$
class Solution {//两个方法。2.通项公式
public:
    int fib(int n) {
        if(n==0) return 0;//特殊情况
        double root5 = sqrt(5);
        return (1/root5)*(pow((1+root5)/2,n)-pow((1-root5)/2,n));
    }
};