斐波那契数列

题目描述

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从 0 开始，第 0 项为 0。(n≤39)

样例

输入整数 n=5 

返回 5

题解

斐波那契数列：前两项为1， 从第三项之后，每一项的纸是前两项的和
f ( x ) = { 1 , x = 1 1 , x = 2 f ( x − 1 ) + f ( x − 2 ) , x > 2 f(x) = \begin{cases} 1, &\text{x = 1} \\ 1, &\text{x = 2} \\ f(x-1) + f(x-2), & \text{x > 2} \end{cases} f(x)=⎩⎪⎨⎪⎧​1,1,f(x−1)+f(x−2),​x = 1x = 2x > 2​

直接递推即可,数据量也没有爆， 不用高精度

class Solution {
public:
    int Fibonacci(int n) {
        int f[41] = {0};
        f[1] = 1, f[2] = 1;
        for (int i = 3; i <= n; i ++)
            f[i] = f[i-1] + f[i-2];
        
        return f[n];
    }
};