看到“斐波那契数列”是不是很多人立刻就写了一个 a[1] = 1; a[2] = 2;

a[i] = a[i - 1] + a[i - 2];

然后跑样例，发现错了？

其实我开始也是这么做的（）

这道题还是在找规律

如果愿意花点时间看每一阶有多少走法，其实就能发现规律

第一阶：1 一种

第二阶：1 - 1， 1 - 2 两种

第三阶：1 - 1 - 1， 1 - 2， 2 - 1， 3 四种

第四阶：1 - 1 - 1 - 1， 1 - 1 - 2， 1 - 2 - 1， 2 - 1 - 1， 2 - 2， 1 - 3， 3 - 1 七种 ......

前三阶没有规律，从第四阶开始就可以发现等于前三阶走法之和

那就很简单了，可以写出递归式

cin >> x;

a[1] = 1;
a[2] = 2;
a[3] = 4;

for (int i = 4; i <= n; i++)
{
    a[i] = a[i - 1] + a[i - 2] + a[i - 3];
}

cout << a[x] << endl;

如果你以为这就完了，那就大错特错了，题目中说了要模1000000007

那把输出改成a[x] % 1000000007？

还是错了

要把每一步运算结果都模1000000007

最终AC程序：

#include <bits/stdc++.h>

using namespace std;

long long n, ans, a[1005];

int main()
{
    cin >> n;

    a[1] = 1;
    a[2] = 2;
    a[3] = 4;

    for (int i = 4; i <= n; i++)
    {
        a[i] = a[i - 1] + a[i - 2] + a[i - 3];
        a[i] %= 1000000007;
    }

    cout << a[n] << endl;

    return 0;
}

#include <iostream>
using namespace std;
const long long mod = 1000000007;
long long x = 3,ans = 7,pree = 1,pre = 2,now = 3,n = 0;
int main()
{
	cin >> n;
	for (int i = 5;i <= n;i++)
	{
		x = ((pree % mod) + (pre % mod) + (now % mod) % mod);
		pree = pre;
		pre = now;
		now = x;
		ans += x;
		ans %= mod;
	}
	if (x == 4) ans = 7;
	if (x == 3) ans = 4;
	if (x == 1 || x == 2) ans = x;
	cout << ans;
	return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int n, a[1000005];
    cin >> n;
    a[1] = 1;
    a[2] = 2;
    a[3] = 4;
    for (int i = 4; i <= n; i++)
    {
        a[i] = a[i - 1] + a[i - 2] + a[i - 3];
        a[i] %= MOD;
    }
    cout << a[n];
    return 0;
}

题解如下

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
ll n, a[1005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    a[1] = 1;
    a[2] = 2;
    a[3] = 4;
    for (int i = 4; i <= n; i++)
        a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % MOD;
    cout << a[n];
    return 0;
}

这个其实有一个思路 （a+c）%b=(a%b+c%b)%b 可以先用define预设一个long long 代码如下

#include <bits/stdc++.h> #define ll long long using namespace std; const ll MAX=1000000007; ll n,a[1005]; int main(){ cin>>n; a[1]=1; a[2]=2; a[3]=4; for(ll i=4;i<=n;i++) a[i]=a[i-1]%MAX+a[i-2]%MAX+a[i-3]%MAX; cout<<a[n]%MAX; return 0; }

洛谷原题：台阶问题

#include <iostream>
using namespace std;
int main()
{
    long long n,a[10000005];
    cin>>n;
    a[0]=1,a[1]=1;
    for (int i=2;i<=n;i++)
    {
        for (int j=1;j<=3;j++)
        {
            if (i>=j) a[i]+=a[i-j];
            a[i]%=1000000007;
        }
    }
    cout<<a[n]%1000000007;
    return 0;
}

洛谷原题:台阶问题

https://www.luogu.com.cn/problem/P1192

[普及]跳台阶

题目背景

跳台阶的题目不陌生,类似于斐波那契数列,使用递归或者递推求解。

题目描述

楼梯有n个台阶,一次可以跳上1,2或3阶,那么总共有多少种方法可以上完n阶台阶呢?

输入格式

一个正整数n,表示有n个台阶。

输出格式

一个数字,表示方法数量,由于结果很大,要输出对1000000007取余的结果。

样例

输入数据1

4

输出数据1

7

输入数据2

30

输出数据2

53798080

输入数据3

100

输出数据3

347873931

数据范围

对于60%的数据:n≤30。

对于100%的数据:n≤1000。

提示

使用普通的递归可以获得60分,但对于100%的数据会超时,你需要加一些手段,或者直接使用递推。

代码:(已化最简)

#include<iostream>
using namespace std;
int main(){
long long a[1000],b,c;cin>>b;
a[1]=1;a[2]=2;a[3]=4;
for(c=4;c<=b;c++){a[c]=a[c-1]+a[c-2]+a[c-3];a[c]%=1000000007;}
cout<<a[b];
return 0;
}

记忆化搜索： 步骤：

1. 定义数组，储存结果。
2. 定义递归函数。
3. 如果到达递归边界，直接返回，如果这个数求过了，也直接返回。
4. 递归调用
5. 输入
6. 调用函数

作用：优化递归
AC代码：

#include <bits/stdc++.h>
using namespace std;
//1. 定义数组
long long n,f[1005];
//2. 定义递归函数
long long fib(long long x)
{
    //3. 处理递归边界和已经算过的结果
    if (x == 1)
    {
        return 1;
    }
    if (x == 2)
    {
        return 2;
    }
    if (x == 3)
    {
        return 4;
    }
    if (f[x])
    {
        return f[x];
    }
    //4. 递归调用
    f[x] = (fib(x - 1) % 1000000007 + fib(x - 2) % 1000000007 + fib(x - 3) % 1000000007) % 1000000007;
    return f[x];
}
int main()
{
    //5. 输入
    cin >> n;
    //6. 调用函数
    cout << fib(n);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long ttj[100000000], n;
int main(){
    cin >> n;
    ttj[1] = 1;
    ttj[2] = 2;
    ttj[3] = 4;
    for (int i = 4; i <= n; i++){
        ttj[i] = ttj[i - 1] + ttj[i - 2] + ttj[i - 3];
        ttj[i] %= 1000000007;
    }
    cout << ttj[n];
}

之前那篇不见了，再来一波

• 假设第一次跳的是一阶，那么剩下的n-1个台阶，跳法是f(n-1)
• 假设第一次跳的是两阶，那么剩下的n-2个台阶，跳法是f(n-2)
• 假设第一次跳的是三阶，那么剩下的n-3个台阶，跳法是f(n-3)

所以f(n) = f(n-1) + f(n-2)+f(n-3) 然而，我相信此时一定有人 和我一样

f[1]=1;
f[2]=2;
f[3]=3;

事实上：

SO:

f[1]=1;
f[2]=2;
f[3]=4;

你们最想要的AC代码嘛

抄题解的人太多了，直接复制粘贴，你平时在学校里考试也是直接抄别人的吗？ —— C++源老师(b站tarjan98) (wsy1998)

还是贴上吧：

#include <bits/stdc++.h>
using namespace std;
long long n,f[1005];//数据开太小，亲人两行泪
int main()
{
    cin >> n;
    f[1] = 1;
    f[2] = 2;
    f[3] = 4;
    for (int i = 4; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2] + f[i - 3];
        f[i] %= 1000000007;//记得取模
    }
    
    cout << f[n] << endl;
    
    return 0;

}

#include<bits/stdc++.h>
using namespace std;
int n;
long long k[2010];//记忆化搜索+递归
long long f(int a){
    if(a==1||a==2)
        return a;
    else if(a==3)
		return 4;
    if(k[a])
        return k[a];
    k[a]=(f(a-1)+f(a-2)+f(a-3))%1000000007;
    return k[a];
}
int main(){
    cin>>n;
    cout<<f(n);
    return 0;
}

直接递推即可，就是真搞不懂为什么python没有数字大小的限制？

List=[1,2,4]
start=3
for i in range(3,1000):
    List.append(List[i-1]+List[i-2]+List[i-3])#暴力打表
a=int(input())
print(List[a-1]%1000000007)#就离谱，直接对1000000007取余也可以。

Loading:24/100……

a[1]=1;//初始化
a[2]=2;
a[3]=4;
for (int i=4;i<=n;i++)
{
    a[i]=(a[i-3]+a[i-2]+a[i-1])%1000000007;//对计算出的每一项取模
}

鼓励大家写题解，但注意题解格式。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

啥叫“模1000。。。7”？

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a[10000005],n;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(i<=3){
            a[i]=i;
            if(i==3)a[i]++;
        }else a[i]=(a[i-1]+a[i-2]+a[i-3])%1000000007;//取模
    }cout<<a[n];
    return 0;

#include<bits/stdc++.h>
using namespace std;
int main(){
    //方法1
    long long a[10000005],n;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(i<=3){
            a[i]=i;
            if(i==3)a[i]++;
        }else a[i]=(a[i-1]+a[i-2]+a[i-3])%1000000007;//取模
    }cout<<a[n];
    return 0;
}/*方法2
int b(int x){
    if(x<=2)return x;
    if(x==3)return 4;
    if(a[x])return a[x];
    a[x]=(b(x-1)+b(x-2)+b(x-3))%1000000007;
    return a[x];
}long long a[10000005],n;备忘录
cin>>n;
cout<<b(n);
*/

#include <iostream> using namespace std;

const int MOD = 1000000007;

int main() { int n; cin >> n;

// 初始化
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;

// 动态转移方程
for (int i = 3; i <= n; i++) {
    dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD;
}

cout << dp[n] << endl;

return 0;

}

我这样做的

#include <iostream>//hetao3097453
using namespace std;
long long  a[1001];
int main()
{
    int n;
    cin >> n;
    a[1] = 1;//递推
    a[2] = 2;
    a[3] = 4;
    for(int i = 4;i <= n;i++)
    {
        a[i] = (a[i - 1] + a[i - 2] + a[i - 3]);
        a[i] %= 1000000007;//对1000,000,007取余；
    }
    cout << a[n];
    return 0;
}

注意一点：用来存储递推结果的数组（a）一定要使用long long !

int 只能得60分！！！

int 只能得60分！！！

long long a[10005]

而不是

int a[10005]

!