O(1)!

class Solution {
private:
    static constexpr int a[40] = {
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,
        1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,
        196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887,
        9227465, 14930352, 24157817, 39088169, 63245986 };
public:
    int Fibonacci(int n) {
        return a[n];
    }
};

6

666

66666666666666666666666666666

36/6，除了6还是

O(1)！！打表万岁！！

面相结果编程！

6

999

除了6还是6

逆天

牛

编程来源于数学（确信）

666

没办法，就是喜欢节省内存

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

感觉好像有点巧妙，有点dp的味道

## O(N) dp大内存法
试试无编辑器写markdown

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

这种还是不科学。还是传递的好，只记录三个数

int Fibonacci(int n) {
        int a = 0, b = 1;
        int t;
        while(n--)
        {
            t = a + b;
            a = b;
            b = t;
        }
        return a;
    }

万物皆可dp，不过打表是真的好用hh

如果n=0的时候会出现数组越界，需要加一个判0；

又学一招“滚动数组”，特别棒！矩阵求法，最后变成快速幂也太 6 了。

y总 为什么是n–而不是n++呢

因为要循环n次啊，为啥要++?

为什么求的过程放在函数外面会报错？
class Solution {
public:
int a[40];
a[0] = 0; a[1] = 1;
for (int i = 2;i < 40;i ++){
a[i] = a[i - 1] + a[i - 2];
}
int Fibonacci(int n) {
return a[n];
}
};

建议你先去学c++

$G_f$

# feng

我**的，我做出了啥？？？
语言：C
#include[HTML_REMOVED]
using namespace std;
int main(){
int n,sum=0,z=0,b[10001],c[n];
cin>>n;
int a[n];
for(int i=0;i[HTML_REMOVED]>a[i];
b[sum]=a[i];
for(int x=0;x<=sum+1;x){
if(b[x]==a[i]){
c[z]=b[x]
z++;
}
}
}
if(sum==0){
cout<<”-1”;
}else{
cout<<c[0];
}
return 0;
}

# $\color{green}{6}$

对的

不知为何，为啥这题库不接受这种格式

#include[HTML_REMOVED]
using namespace std;
int main()
{
int a ,b, c,k;
cin>>k;
a=1;
b=1;
c=1;
for( int i=3;i<=k;i++)
{
a=b;
b=c;
c=a+b;
}
cout<<c;
return 0;
}

???

# $O(1)$!!!!!
用一下熟悉的通项公式：
$$ f_i=\frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right] $$
然后直接套就完了

class Solution {
public:
    int Fibonacci(int n) {
        double c1 = (1.0 + sqrt(5)) / 2, c2 = (1.0 - sqrt(5)) / 2;
        return (int)((pow(c1, n) - pow(c2, n)) / sqrt(5));
    }
};

考虑一下pow和sqrt的复杂度。

赞同，之前有个人 用了 sort，然后说自己 O(1)，被别人质疑了，还说 没有写循环，就是 O(1) 的， 实属funny了

赞同，但这玩意儿偷懒或数据小的时候确实可以用

https://blog.csdn.net/u013095333/article/details/112059935
https://blog.csdn.net/u013445530/article/details/38520021
看起来sqrt没啥，pow还是别用了吧……

tnnd，还是数学牛啊

666
666

66666666

233333

问问y总，像这种只能在给定的函数内写代码，是不是一些特殊的头文件的函数就不能用了？