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次啊，为啥要++?

$O(\log n)$!

#include <bits/stdc++.h>
using namespace std;
struct Mat {
    int a[2][2];
    Mat() {
        memset(a, 0, sizeof a);
    }
    int* operator[] (int i) {
        return a[i];
    }
    Mat operator * (Mat& b) {
        Mat c;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    c[i][j] = (c[i][j] + (a[i][k] * b[k][j]));
        return c;
    }
};
Mat qpow(Mat& a, int n) {
    Mat ans;
    ans[0][0] = ans[0][1] = ans[1][0] = ans[1][1] = 1;
    while (n) {
        if (n & 1) ans = ans * a;
        n >>= 1;
        a = a * a;
    }
    return ans;
}
class Solution {
public:
    int Fibonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        Mat m;
        m[0][0] = 1; m[0][1] = 1; m[1][0] = 1; m[1][1] = 0;
        Mat ans = qpow(m, n - 2);
        return ans[0][0];
    }
};

为什么求的过程放在函数外面会报错？
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;
}

???

#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总，像这种只能在给定的函数内写代码，是不是一些特殊的头文件的函数就不能用了？